leetcode回溯+剪枝（排列,組合,子集問題）

排列問題

46. 全排列

給定一個不含重複數字的數組 nums ，傳回其所有可能的全排列。你可以按任意順序傳回答案。

示例 1：

輸入：nums = [1,2,3]

輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

排列問題，采用回溯算法解決，首先将選擇過程想成樹型結構，并通過回溯，得到所有的結果。

排列問題需要考慮順序，此類回溯通用解法，設一個二維數組res儲存所有的結果，一個數組path儲存目前搜尋的路徑，depth表示目前樹中的深度，對于排列問題，設定一個used數組，記錄目前數字是否使用，避免重複使用。

class Solution {
    public List<List<Integer>> permute(int[] nums) { 
    int len=nums.length;
    List<List<Integer>> res=new ArrayList<>();
    if(len==0)return res;
    boolean[] used=new boolean[len];
    List<Integer> path=new ArrayList<>();
    dfs(nums,len,0,path,used,res);
    return res;
    }
    public void dfs(int nums[],int len,int depth,List<Integer> path,boolean[] used,List<List<Integer>> res){
        if(depth==len){
            //res.add(path);
            //為什麼會出現空了。實際上path也确實被加進去了，但是由于Java的特性，下次遞歸的時候，實際上是又在修改這個path，以及相應的res，緻使在最後一次遞歸複原的時候，把path加入的東西全吐出來了
            res.add(new ArrayList<>(path));//達到最深處，将目前路徑添加到結果中
            return;
        }
        for(int i=0;i<len;i++){
            if(!used[i]){
                path.add(nums[i]);
                used[i]=true;
                dfs(nums,len,depth+1,path,used,res);//遞歸的執行下一層。
                used[i]=false;//回溯過程，退回一個。
                path.remove(path.size()-1);
            }
        }
    }
}

全排列 II

給定一個可包含重複數字的序列 nums ，按任意順序傳回所有不重複的全排列。

示例 1：

輸入：nums = [1,1,2]

輸出：

[[1,1,2],

[1,2,1],

[2,1,1]]

與上一題的差別是，這個nums中包含重複的數字，要處理掉重複的結果，進行剪枝。

先把數字排序，在有序的條件下

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])

因為數組是有序的，nums[i-1]是前一個撤銷的數字，如果目前的值和前一個撤銷的數字相同，即可進行剪枝（cntinue）。例如：目前路徑中為1，2，前一個撤銷的數字為3；說明1，2，3開頭的排列都已經找完了，如果nums[i]還等于3，即可剪枝跳過，去掉重複的值。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
    int len=nums.length;
    List<List<Integer>> res=new ArrayList<>();
    if(len==0)return res;
    Arrays.sort(nums);//先經過排序，後續剪枝的num[i-1]才能保證是上一步撤銷的值。
    boolean[] used=new boolean[len];
    // 使用 Deque 是 Java 官方 Stack 類的建議
    Deque<Integer> path = new ArrayDeque<>(len);
    dfs(nums,len,0,path,used,res);
    return res;
    }
    public void dfs(int nums[],int len,int depth,Deque<Integer> path,boolean[] used,List<List<Integer>> res){
        if(depth==len){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<len;i++){
            if (used[i]) {
                continue;
            }
            // 剪枝條件：i > 0 是為了保證 nums[i - 1] 有意義
            // 寫 !used[i - 1] 是因為 nums[i - 1] 在深度優先周遊的過程中剛剛被撤銷選擇
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums, len, depth + 1, path, used, res);
            // 回溯部分的代碼，和 dfs 之前的代碼是對稱的
            used[i] = false;
            path.removeLast();
        }
}}

組合問題

39. 組合總和

給定一個無重複元素的正整數數組 candidates 和一個正整數 target ，找出 candidates 中所有可以使數字和為目标數 target 的唯一組合。

candidates 中的數字可以無限制重複被選取。如果至少一個所選數字數量不同，則兩種組合是唯一的。

對于給定的輸入，保證和為 target 的唯一組合數少于 150 個。

示例 1：

輸入: candidates = [2,3,6,7], target = 7

輸出: [[7],[2,2,3]]

組合問題差別于排列，不使用used[]數組，如果使用used數組，當選擇了1後，再選擇2；如果選擇了2，used[1]還是0，可以被選擇，是以會産生兩個重複的組合。

是以組合不使用used數組，而是用begin，在數組有序的情況下，不會選擇前面的數字。

例如path[1,2]，begin=2，不會再去尋找前面的值

和為7，根節點為7，嘗試減去給定數組的各個值，如果最後在葉子節點中能夠減為0，則該路徑上的值的和為target。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    int len=candidates.length;
    List<List<Integer>> res=new ArrayList<>();
    Deque<Integer> path=new ArrayDeque<>(len);
    Arrays.sort(candidates);//一定要排序
    if(len==0)return res;
    dfs(candidates,len,0,path,res,target);//初始begin起始點為0
    return res;
    }
    public void dfs(int[] nums, int len, int begin, Deque<Integer> path, List<List<Integer>> res,int target){
        if(target==0){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=begin;i<len;i++){
            if(target-nums[i]<0){//剪枝條件
                break;
            }
            path.addLast(nums[i]);
            dfs(nums,len,i,path,res,target-nums[i]);
            path.removeLast();
        }
    }
}

組合總和 II

給定一個數組 candidates 和一個目标數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中隻能使用一次。

注意：解集不能包含重複的組合。

輸入: candidates = [10,1,2,7,6,1,5], target = 8,

輸出:

[

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

與上一題的差別是每個數字隻能使用一次。

遞歸的dfs中，傳遞的begin值為i+1，因為每個元素隻能使用一次。

public class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 關鍵步驟
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates, len, 0, target, path, res);
        return res;
    }
    private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }//數組中有多個相同數字，保證不産生重複的結果。
            path.addLast(candidates[i]);
            // 因為元素不可以重複使用，這裡遞歸傳遞下去的是 i + 1 而不是 i
            dfs(candidates, len, i + 1, target - candidates[i], path, res);
            path.removeLast();
        
        }
    }


}

組合

給定兩個整數 n 和 k，傳回範圍 [1, n] 中所有可能的 k 個數的組合。

你可以按任何順序傳回答案。

輸入：n = 4, k = 2

輸出：

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

也是一個不能重複選擇的組合，多了個參數k，找到指定的個數的即可。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        int[] candidates=new int[n+1];
        for(int i=1;i<=n;i++){
            candidates[i]=i;
        }
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates, len, 1, path, res,k,0);
        return res;
    }
    private void dfs(int[] candidates, int len, int begin,Deque<Integer> path, List<List<Integer>> res,int k,int depth) {
        if(depth==k){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=begin;i<len;i++){
            path.addLast(candidates[i]);
            dfs(candidates, len, i + 1, path, res,k,depth+1);
            path.removeLast();
        }
    }
}

子集

給你一個整數數組 nums ，數組中的元素互不相同。傳回該數組所有可能的子集（幂集）。

解集不能包含重複的子集。你可以按任意順序傳回解集。

本質也是組合，不過函數每次執行都把目前路徑加到結果中，保證子集都考慮。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 關鍵步驟
        Arrays.sort(nums);
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(res,nums,path,0,len);
        return res;
    }
    private void dfs(List<List<Integer>> res,int[] nums,Deque<Integer> path,int begin,int length) {
        res.add(new ArrayList<>(path));
        for(int i=begin;i<length;i++){
            path.addLast(nums[i]);
            dfs(res,nums,path,i+1,length);
            path.removeLast();
        }
    }
}

子集 II

給你一個整數數組 nums ，其中可能包含重複元素，請你傳回該數組所有可能的子集（幂集）。

解集不能包含重複的子集。傳回的解集中，子集可以按任意順序排列。

與上一道題的差別是，nums中可能包含重複元素。與之前的組合類似，需要進行剪枝，如果nums[i]==nums[i-1]就進行剪枝。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
      int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 關鍵步驟
        Arrays.sort(nums);
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(res,nums,path,0,len);
        return res;
    }
    private void dfs(List<List<Integer>> res,int[] nums,Deque<Integer> path,int begin,int length) {
        res.add(new ArrayList<>(path));
        for(int i=begin;i<length;i++){
            if(i>begin&&nums[i]==nums[i-1]){
               continue;
            }
            path.addLast(nums[i]);
            dfs(res,nums,path,i+1,length);
            path.removeLast();
        }
}
}

排列序列

給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列。

按大小順序列出所有排列情況，并一一标記，當 n = 3 時, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

給定 n 和 k，傳回第 k 個排列。

如果采用回溯法解決，很容易逾時，是以要采用正确的剪枝方法，我的做法是，本題求第k個，當搜尋到第k個之後就直接結束回溯，不在繼續後面的，但是這樣也很浪費時間。

把遞歸函數設定為布爾型，把遞歸函數的執行放到if條件判斷中，保證執行

class Solution {
    boolean[] def;
    StringBuilder res;
    int count;
    int k;
    int n;
    public String getPermutation(int n, int k) {
        this.k = k;
        this.n = n;
        def = new boolean[n+1]; // 哈希表做通路标記
        count++;
        res = new StringBuilder(); // 可變res
        dfs(0);
        return res.toString();
    }
    boolean dfs(int depth){
        if(depth == n){
            if(count == k){ // 說明已經找到了第 k 個，直接傳回true，友善剪枝
                return true;
            }
            else{
                ++count; // 還沒找到第 k 個，是以count自增，并且傳回false。
                return false;
            }
        }
        for(int i = 1;i <= n;++i){
            if(def[i]) continue; // 已通路元素直接略過，i從1開始保證了k個結果的大小順序
            def[i] = true; // 未通路元素先做标記
            res.append(i); 
            if(dfs(depth+1)) return true; // 大剪枝，也就是說找到了元素，此後就不必再找了
            res.deleteCharAt(res.length()-1); // 每次删除res的最後一個字元，回溯。
            def[i] = false; // 恢複未通路标記
        }
        return false;
    }
}

看了回溯的高效解法，當搜尋進行到某一層時，先檢視該點下面一共有多少種可能，如果小于給定的k，可以直接進行剪枝，因為就算把下面的路徑都搜尋出來，也達不到k。

import java.util.Arrays;

public class Solution {

    private boolean[] used;

    /**
     * 階乘數組
     */
    private int[] factorial;

    private int n;
    private int k;

    public String getPermutation(int n, int k) {
        this.n = n;
        this.k = k;
        calculateFactorial(n);

       
        used = new boolean[n + 1];
        Arrays.fill(used, false);

        StringBuilder path = new StringBuilder();
        dfs(0, path);
        return path.toString();
    }


    /**
     * @param index 在這一步之前已經選擇了幾個數字，其值恰好等于這一步需要确定的下标位置
     * @param path
     */
    private void dfs(int index, StringBuilder path) {
        if (index == n) {
            return;
        }

        // 計算還未确定的數字的全排列的個數，第 1 次進入的時候是 n - 1
        int cnt = factorial[n - 1 - index];
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (cnt < k) {
                k -= cnt;//目前點之下可能的結果達不到k，直接換下一個，并從k中減去。
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(index + 1, path);
            // 注意 1：不可以回溯（重置變量），算法設計是「一下子來到葉子結點」，沒有回頭的過程
            // 注意 2：這裡要加 return，後面的數沒有必要周遊去嘗試了
            return;
        }
    }

    /**
     * 計算階乘數組
     *
     * @param n
     */
    private void calculateFactorial(int n) {
        factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }
}

字母大小寫全排列

給定一個字元串S，通過将字元串S中的每個字母轉變大小寫，我們可以獲得一個新的字元串。傳回所有可能得到的字元串集合。

示例：

輸入：S = “a1b2”

輸出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

輸入：S = “3z4”

輸出：[“3z4”, “3Z4”]

輸入：S = “12345”

輸出：[“12345”]

此題雖說是字元串的排列，但實際上字母的順序并不能改變，不能用used數組，應該用begin設定初始值。

遇到數字，直接進行遞歸回溯，如果是字母，先将其大寫字母進行遞歸回溯，再将其小寫字母遞歸回溯即可。

class Solution {

    private List<String> res = new ArrayList<>();
    public List<String> letterCasePermutation(String s) {

        StringBuilder sb = new StringBuilder();

        backtrack(s, 0, sb);
        return res;
    }

    public void backtrack(String s, int start, StringBuilder sb) {

        if (sb.length() == s.length()) {

            res.add(sb.toString());
            return ;
        }

        for (int i=start;i<s.length();i++) {

            char c = s.charAt(i);

            if (Character.isDigit(c)) {

                sb.append(c);
                backtrack(s, i + 1, sb);
                sb.deleteCharAt(sb.length() - 1); // 撤銷選擇
            } else {

                char A = Character.toUpperCase(c);//大寫執行一遍
                sb.append(A);
                backtrack(s, i + 1, sb);
                sb.deleteCharAt(sb.length() - 1);

                char a = Character.toLowerCase(c);//小寫執行一遍
                sb.append(a);
                backtrack(s, i + 1, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}

leetcode回溯+剪枝（排列,組合,子集問題）

繼續閱讀

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程式設計

leetcode809

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希