回溯常见问题总结

组合问题

代码随想录看完回溯文章后自己问题的总结

77. 组合

题目连接：https://leetcode.cn/problems/combinations/
剪枝前代码

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTrack(1,k,n);
        return res;
    }
    void backTrack(int start,int k,int n){
        if(path.size()==k){
            res.add(new ArrayList<>(path));
             return;
        }
        for(int i=start;i<=n;i++){
            path.add(i);
            backTrack(i+1,k,n);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剪枝就是对for循环进行操作。
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
剪枝后代码

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTrack(1,k,n);
        return res;
    }
    void backTrack(int start,int k,int n){
        if(path.size()==k){
            res.add(new ArrayList<>(path));
             return;
        }
        for(int i=start;i<=n-(k-path.size())+1;i++){
            path.add(i);
            backTrack(i+1,k,n);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

216组合总和 III

题目连接：https://leetcode.cn/problems/combination-sum-iii/
在上一题的基础上进行了延伸，加入了总和的情况
剪枝前

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        int sum=0;
        backTrack(1,k,n,sum);
        return res;
    }
    void backTrack(int start,int k,int n,int sum){
        if(k==path.size()){
            if(sum==n){
                res.add(new ArrayList<>(path));
                return;
            }
        }
        if(path.size()>k){
            return;
        }
        if(sum>n){
            return;
        }
        for(int i=start;i<=9;i++){
            sum+=i;
            path.add(i);
            backTrack(i+1,k,n,sum);
            sum-=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
26
27
28
29
30

剪枝后

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        int sum=0;
        backTrack(1,k,n,sum);
        return res;
    }
    void backTrack(int start,int k,int n,int sum){
        if(k==path.size()){
            if(sum==n){
                res.add(new ArrayList<>(path));
                return;
            }
        }
        if(path.size()>k){
            return;
        }
        if(sum>n){
            return;
        }
        for(int i=start;i<=9-(k-path.size())+1;i++){
            sum+=i;
            path.add(i);
            backTrack(i+1,k,n,sum);
            sum-=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
26
27
28
29
30

39.组合总和

题目连接：https://leetcode.cn/problems/combination-sum/
这个题和上一个的区别是本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
不少同学都是看到可以重复选择，就义无反顾的把startIndex去掉了。
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
如果是一个集合来求组合的话，就需要startIndex例如 求组合问题和求组合总和

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：电话号码字母总和

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        traverse(candidates,0,0,target);
        return res;
    }
    void traverse(int[] candidates,int sum,int start,int target){
        if(sum==target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum>target){
            return;
        }
        for(int i=start;i<candidates.length;i++){
            path.add(candidates[i]);
            sum+=candidates[i];
            traverse(candidates,sum,i,target);
            path.removeLast();
            sum-=candidates[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

40组合总和 ||

题目连接：https://leetcode.cn/problems/combination-sum-ii/
要求是：candidates 中的每个数字在每个组合中只能使用 一次 。解集不能包含重复的组合。

难点在于去重问题。
层之间的去重就是加入start下标来保证下一层不会用到上一层下标的元素。
而对于同一层来说，去重就是（前提数组是排好序的）剪枝逻辑，值相同的相邻树枝，只遍历第一条。
代码体现

if(i>start&&candidates[i]==candidates[i-1]){
                continue;
            }
1
2
3

完整代码

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrack(candidates,0,0,target);
        return res;
    }
    void backTrack(int[] candidates,int start,int sum,int target){
        if(sum==target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum>target){
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(i>start&&candidates[i]==candidates[i-1]){
                continue;
            }
            sum+=candidates[i];
            path.add(candidates[i]);
            backTrack(candidates,i+1,sum,target);
            sum-=candidates[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
26
27
28

17. 电话号码的字母组合

题目连接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
此题就属于多个集合求组合，无需多言，看代码

class Solution {
    List<String> res=new ArrayList<>();
    String[] map=new String[]{
        "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
    };
    StringBuilder sb=new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){
            return res;
        }
        traverse(digits.toCharArray(),0);
        return res;
    }
    void traverse(char[] digits,int start){
        if(start>=digits.length){
            res.add(sb.toString());
            return;
        }
        String tmp=map[digits[start]-'0'];
        for(int i=0;i<tmp.length();i++){
            sb.append(tmp.charAt(i));
            traverse(digits,start+1);
            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

131. 分割回文串

题目连接：https://leetcode.cn/problems/palindrome-partitioning/
思路：其实分割回文串就类似组合问题，主要处理几个问题，如何判断回文，如何去模拟每个被分割成的子串（这里每个子串都是从start开始的），何时终止递归

class Solution {
    List<List<String>> res=new ArrayList<>();
    LinkedList<String> path=new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTrack(s,0);
        return res;
    }
    void backTrack(String s,int start){
        if(start>=s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=start;i<s.length();i++){
            if(ispardr(s,start,i)){
                path.add(s.substring(start,i+1));
            }else{
                continue;
            }
            backTrack(s,i+1);
            path.removeLast();
        }
    }
  boolean  ispardr(String s,int left,int right){
      while(left<=right){
          if(s.charAt(left)==s.charAt(right)){
              left++;
              right--;
          }else{
              return false;
          }
      }
      return true;
  }
}
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

子集问题

78.子集

题目连接：https://leetcode.cn/problems/subsets/
思路：做过组合问题自然而然就知道子集问题如何解答，组合问题就是把回溯树的叶子结点加入结果集，子集问题就是就是把所有结点都加入结果集。

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTrack(nums,0);
        return res;
    }
    void backTrack(int[] nums,int start){
        res.add(new ArrayList<>(tmp));
        for(int i=start;i<nums.length;i++){
            tmp.add(nums[i]);
            backTrack(nums,i+1);
            tmp.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

90. 子集 II

题目连接：https://leetcode.cn/problems/subsets-ii/
思路：和上一个子集问题类似，只不过加入了数组可能包含重复元素，解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
说白了 就是子集问题加上去重呗，相同的树枝用一次（排序）

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTrack(nums,0);
        return res;
    }
    void backTrack(int[] nums,int start){
        res.add(new ArrayList<>(tmp));
        for(int i=start;i<nums.length;i++){
            if(i>start&&nums[i]==nums[i-1]){
                continue;
            }
            tmp.add(nums[i]);
            backTrack(nums,i+1);
            tmp.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

491. 递增子序列

题目连接：https://leetcode.cn/problems/increasing-subsequences/
思路：子序列乍一看像一个有序的子集，又需要去重，果断就想到了上一个问题 子集||了，但是题目要求结果是递增子序列，子集|| 的思想是先排序然后加去重，这里就不能像上一题那样做了，这道题不能改变 nums 的原始顺序，所以不能用排序的方式，而是用 used 集合来避免重复使用相同元素。

让子序列递增的代码体现

if(tmp.size()>=2){
            res.add(new ArrayList<>(tmp));
        }
1
2
3

去重的代码体现

if(used.contains(nums[i])){
                continue;
            }
1
2
3

完整代码

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTrack(nums,0);
        return res;
    }
    void backTrack(int[] nums,int start){
        if(tmp.size()>=2){
            res.add(new ArrayList<>(tmp));
        }
        Set<Integer> used=new HashSet<>();
        for(int i=start;i<nums.length;i++){
            if(!tmp.isEmpty()&&tmp.getLast()>nums[i]){
                continue;
            }
            if(used.contains(nums[i])){
                continue;
            }
            used.add(nums[i]);
            tmp.add(nums[i]);
            backTrack(nums,i+1);
            tmp.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

排列问题

排列问题和组合子集问题最大的区别就是加入的顺序的概念

46. 全排列

题目连接：https://leetcode.cn/problems/permutations/
思路：引入了used数组就是保证了一个问题，当前层的一个元素加入到了结果集子集里面了，ok那么这个元素就不能用了到下一层的时候除了这个之外的元素还是可以用的，在used数组里面的代表已经用过的元素。

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> tmp=new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used=new boolean[nums.length];
        backTrack(nums);
        return res;
    }
    void backTrack(int[] nums){
        if(tmp.size()==nums.length){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i]=true;
            tmp.add(nums[i]);
            backTrack(nums);
            used[i]=false;
            tmp.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

47. 全排列 II

题目连接：https://leetcode.cn/problems/permutations-ii/
思路：全排列加上去重操作
包含重复数字的序列第一想法就是先排序
层之间的去重代码体现：

if(used[i]){
                continue;
            }
1
2
3

树枝之间的去重体现：思想就是如果两个树枝相同并且前一个还没有使用就continue

if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){
                continue;
            }
1
2
3

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used=new boolean[nums.length];
        backTrack(nums);
        return res;
    }
    void backTrack(int[] nums){
        if(path.size()==nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){
                continue;
            }
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            backTrack(nums);
            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

N皇后问题

算法课一定绕不开的一道问题。。。。。。
题目连接：https://leetcode.cn/problems/n-queens/
思路：合法性的判断：行 列 斜线 都要判断
这里 每行只有一个就不用判断了，所以要判断 列还有元素所在的左上和右上的两条斜线
backTrack函数的参数也很简单一个防止元素的数组还有一个就是行
递归出口，当行达到数组行元素最大值之后就加入结果集

class Solution {
    List<List<String>> res=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board=new char[n][n];
        for(char[] c:board){
            Arrays.fill(c,'.');
        }
        backTrack(board,0);
        return res;
    }
    void backTrack(char[][] board,int row){
        if(row==board.length){
            res.add(charToList(board));
            return;
        }
        for(int i=0;i<board[row].length;i++){
            if(!isLegal(board,row,i)){
                continue;
            }
            board[row][i]='Q';
            backTrack(board,row+1);
            board[row][i]='.';
        }
    }
    List<String> charToList(char[][] board){
        List<String> list=new ArrayList<>();
        for(char[] c:board){
            list.add(String.copyValueOf(c));
        }
        return list;
    }
    boolean isLegal(char[][] board,int row,int col){
        //列上面得检查
        for(int i=0;i<board[0].length;i++){
            if(board[i][col]=='Q'){
                return false;
            }
        }
        //左上的验证合法性
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        //右上的验证合法性
        for(int i=row-1,j=col+1;i>=0&&j<board[0].length;i--,j++){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
}
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

37. 解数独

题目连接：https://leetcode.cn/problems/sudoku-solver/
思路：和N皇后思路类似。
合法性判断：题中说了
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
backTrack函数参数一个是数组还有一个就是要放入数字的横纵坐标i，j
想一下要干什么，是往棋盘里面放元素吧，但传入的参数里面没有元素，但回看到题目棋盘里面只能放1到9，所以遍历这1到9的字符不就行了。
再继续细化，并不是 1 到 9 都可以取到的，有的数字不是不满足数独的合法条件吗？而且现在只是给 j 加一，那如果 j 加到最后一列了，怎么办？

很简单，当 j 到达超过每一行的最后一个索引时，转为增加 i 开始穷举下一行，并且在穷举之前添加一个判断，跳过不满足条件的数字：

class Solution {
    public void solveSudoku(char[][] board) {
        backTrack(board,0,0);
    }
    boolean backTrack(char[][] board,int i,int j){
        int m=9,n=9;
        if(i==m){
            return true;
        }
        if(j==n){
           return backTrack(board,i+1,0);
        }
        if(board[i][j]!='.'){
           return backTrack(board,i,j+1);
        }
        for(char ch='1';ch<='9';ch++){
            if(!isLegal(board,i,j,ch)){
                continue;
            }
            board[i][j]=ch;
            if(backTrack(board,i,j+1)) return true;
            board[i][j]='.';
        }
        return false;
    }
    boolean isLegal(char[][] board,int a,int b,char ch){
        for(int i=0;i<9;i++){
            if(board[a][i]==ch){
                return false;
            }
            if(board[i][b]==ch){
                return false;
            }
            if(board[(a/3)*3+i/3][(b/3)*3+i%3]==ch){
                return false;
            }
            
        }
        return true;
    }
}
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