回溯

最近提交时间	题目	题目难度	提交次数
1 分钟前	#79 单词搜索	中等	1 次
24 分钟前	#51 N 皇后	困难	2 次
3 小时前	#131 分割回文串	中等	1 次
3 小时前	#22 括号生成	中等	1 次
3 小时前	#39 组合总和	中等	2 次
3 小时前	#17 电话号码的字母组合	中等	1 次
4 小时前	#78 子集	中等	2 次
4 小时前	#46 全排列	中等	3 次

总套路：1、不管三七二十一，先定义出res，2、再定义path（类型可能不同于res内的看情况而变），3、back （内部条件看情况而定） 4、 return

此部分较麻烦，所以代码贴出来，直接背

回溯：

1、子集的for判断条件

2、电话号码终止条件根据start判断， StringBuilder的 deleteCharAt 方法

3、组合总和有序，递归终止条件要return， if内条件总和大于要 break back递归条件传值i

4、括号传值条件 l> n || l<r

5、单词搜索 if( back(board, i, j, words, 0)) 一定要在这个判断里面返回 return 不能直接return

6、分割字符串的终止条件 start>= s.length() 跟i+1的递归条件

7、n皇后先row 后 col 位置不能反结束条件 n== row的时候

# 全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path  = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        back(nums, res, path,used);
        return res;
    }
      public void back(int[] nums, List<List<Integer>> res, LinkedList<Integer> path, boolean[] used){  
        if(path.size() == nums.length){
          // 存值
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i< nums.length; i++){
            if(used[i]){
                continue;
            }
          	// 记录值
            used[i] = true;
            path.add(nums[i]);
           //  递归找值
            back(nums,res, path, used);
           //  经典回溯
            path.removeLast();
            used[i] = false;
        }
      }
}

思路：
  1、经典套路
  2、back内需要定义 used ，判断当前 nums[i] 是否使用，之所以这么定义 是为了防止 [1,1,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

# 子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
    }
}
思路：
  1、经典套路
  2、back 需要单独定义 start位置

1
2
3
4
5
6
7

# 电话号码组合

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        String[] phone = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        back(digits, res, path, phone, 0);
        return res;
    }
    public void back(String digits, List<String> res , StringBuilder path ,String[] phone , int start ){
        if(start == digits.length()){
            res.add(path.toString());
            return;
        }
       char c =  digits.charAt(start);
       String s = phone[c-'0'];
       for(int i = 0; i< s.length(); i++){
           path.append(s.charAt(i));
           back(digits, res ,path, phone, start+1);
           path.deleteCharAt(path.length() -1);
       }
    }
}
思路：
  1、经典套路
  2、需要定义出phone的数组，最好位置 跟2-9对应，方便取数字
  3、也要定义出 start位置 从0开始，（此位置也是根据digits 的长度而定的）
  4、String s = phone[c-'0']; 这个的意思是获取c对应字符的 字符串

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

        }
    }
}
思路：
  1、经典套路
  2、定义sum 跟 start
  3、   if(sum + candidates[i] > target){
                break;
            }
			这个条件判断 要注意

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

# 括号生成

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String>  res = new ArrayList<>();
        String path = "";
        back(res, path, 0, 0 ,n);
        return res;
    }
    public void back(List<String>  res, String path, int left, int right,int  n ){
            if(left> n || right > left){
                return;
            }
            if(path.length() == 2 *n){
                res.add(path);
                return;
            }
            back(res, path+"(", left+1, right, n);
            back(res, path+")", left, right+1, n);
    }
}
思路：
  1、经典套路
  2、back内条件，除去经典条件，还需要传 l 跟 r 的数量
  3、递归终止条件就是 l > n 或者 r > l （这样做的目的就是限制左右括号相等，且限制了数量）
  4、放入结果条件 就是 path 的长度 为 2n， 因为左右括号是两倍的数量
  5、左右双递归 （一步步的加括号）

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

# 分割字符串

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        LinkedList<String> path =  new LinkedList<>();
        back(s, res, path, 0);
        return res;
    }

    public void back(String s, List<List<String>> res, LinkedList<String> path, int start){
        if(start >= s.length()){
            res.add(new ArrayList(path));
            return ;
        }
        for(int i = start; i< s.length(); i++){
            if(isCycle(s, start, i)){
                path.add(s.substring(start, i+1));
            } else {
                continue;
            }
            back(s, res, path , i+1);
            path.removeLast();
        }
        
    }

    public boolean  isCycle(String s, int l, int r){
        if(l> r){
            return false;
        }
        while(l < r){
            if(s.charAt(l) != s.charAt(r)){
                    return false;
            }
            l++;
            r--;
        }
        return true;
    }
}
思路：
  1、经典套路
  2、需要定义开始位置
  3、另外放入条件 是根据是否是回文数判断的

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

# n皇后

class Solution {
    public List<List<String>> solveNQueens(int n) {
         List<List<String>>  res = new ArrayList<>();
         // 构造棋盘
         char[][] chess = new char[n][n];
         // tianchong
         for(char[] c: chess){
             Arrays.fill(c, '.');
         }
         back(res, n, 0, chess);
         return res;
    }
    public void  back(List<List<String>>  res, int n, int row, char[][] chess){
        if(n == row){
            res.add(arrayToList(chess));
            return;
        }

        for(int col = 0; col< n;col++){
            if(isVaild(row,col,n,chess)){
                chess[row][col] = 'Q';
                back(res, n, row+1, chess);
                chess[row][col] = '.';
            }
        }


    }
    public List<String> arrayToList(char[][] chess){
        List<String>  res = new ArrayList<>();
           for(char[] c: chess){
            res.add(new String(c));
         }
         return res;
    }

    public boolean isVaild(int row, int col, int n, char[][] chess){
        // lie
        for(int i = 0; i< row; i++){
            if(chess[i][col] == 'Q'){
                return false;
            }
        }
        // 45
        for(int i = row-1, j= col-1; i>=0&& j>=0; i--,j--){
            if(chess[i][j] == 'Q'){
                return false;
            }
        }
        //135
        for(int i = row-1, j= col+1; i>=0&& j<=n-1; i--,j++){
            if(chess[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
}
思路：
  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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

# 单词搜索

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0;i< board.length;i++){
            for(int j=0;j< board[i].length;j++){
                if(back(board, words, i, j , 0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean back(char[][] board, char[] words, int i , int j ,int k){
        if(board.length<=i || i<0 || j<0 || j>=board[0].length){
            return false;
        }
        if(board[i][j] != words[k]){
            return false;
        }
        if(k == words.length-1){
            return true;
        }
        board[i][j] = '\0';
        boolean res= back(board, words,i+1, j, k+1) || 
            back(board, words,i-1, j, k+1) || 
            back(board, words,i, j+1, k+1) || 
            back(board, words,i, j-1, k+1);
        board[i][j] = words[k]; 
        return res;   
    }
}
思路：
  1、依然是回溯，但是不同于经典套路
  2、直接背

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

编辑

上次更新: 2024/03/26, 9:03:00

← 二叉树 (伪)二分 →