leetcode回溯+剪枝（排列,组合,子集问题）_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);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

47. 全排列 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();
        }
}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

组合问题
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();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

40. 组合总和 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();
        
        }
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

77. 组合

给定两个整数 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();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

78. 子集

给你一个整数数组 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();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

90. 子集 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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

60. 排列序列

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

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
1
2
3
4
5
6

给定 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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

看了回溯的高效解法，当搜索进行到某一层时，先查看该点下面一共有多少种可能，如果小于给定的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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

784. 字母大小写全排列

给定一个字符串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);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43