Posted Updated Leetcode11 minutes read (About 1645 words)0 visits

Backtracking问题总结

Backtracking总结

Backtracking本质上就是DFS，相当于不停地往深处进行dfs，遇到不可能的情况就停止dfs回到上层。
相当于有一些剪枝的DFS。

由于在进行backtracking的时候，在一次recursive中可能有多种情况(for loop)，那么我们在深入到下一层的时候需要已经改变的temporaryVector，但是很关键的一点是当我们完成所有下层的dfs以后，我们需要把temporaryVector变回来，因为我们还有没进行完的for loop要去做。 这种思想在dfs中很常见，比如经常需要把visited[]数组变成true去做dfs，结束后再变回false。

Backtracking模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ReturnVector Solution(input){
    ReturnVector returnVector;
    TemporaryVector temporaryVector;
    dfs(input, returnVector, temporaryVector, index);
    return returnVector;
}

private void dfs(input, returnVector, temporaryVector, index){
    if(Finished some condition){
        returnVector.add(temporaryVector);
        return;
    }

    for(one possible situation in all situations){
        temporaryVector deal with this situation and add it;
        dfs(input, returnVector, temporaryVector, changedIndex);
        temporaryVector return to its original state;
    }
}
  1. N-Queens：NQueen问题，每一行我们只能放一个Queue，对于每一行我们都有N个位置可以放Queue，所以相当于递归深度是O(N)的DFS，每个深度都有N个选择。
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
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new LinkedList<>();
        if(n==0)
            return ans;
        char[][] board = new char[n][n];
        for(int i =0;i<=board.length-1;i++){
            for(int j =0;j<=board[0].length-1;j++){
                board[i][j] = '.';
            }
        }
        
        solve(board, ans, 0);
        return ans;
        
        
    }
    
    private void solve(char[][] board, List<List<String>> ans, int line){
        if(line==board.length){
            List<String> l = helper(board);
            ans.add(l);
            return;
        }
        
        for(int i = 0;i<=board.length-1;i++){
            if(valid(board, line, i)){
                board[line][i] = 'Q';
                solve(board, ans, line+1);
                board[line][i] = '.';
            }
        } 
    }
    
    private boolean valid(char[][] board, int row, int column){
        for(int i =0;i<=board.length-1;i++){
            if(board[row][i]=='Q' || board[i][column]=='Q'){
                return false;
            }
        }

        for(int i = row-1, j=column-1;i>=0 && j>=0;i--, j--){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        
        for(int i = row-1, j=column+1;i>=0&&j<=board.length-1;i--,j++){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        
        return true;
    }
    
    private List<String> helper(char[][] board){
        List<String> ans = new LinkedList<>();
        for(char[] c:board){
            String s = String.valueOf(c);
            ans.add(s);
        }
        return ans;
    }
    
}
  1. Generate Parentheses: 加括号只有两种情况，加(或者加)，所以不用for loop，同时我们helper(ans, left+1, right, n, s+'(');直接在s上加不会改变原来的s，所以结束dfs后也就不用再进行额外的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new LinkedList<>();
        if(n==0)
            return ans;
        int left = 0;
        int right = 0;
        helper(ans, left, right, n, "");
        return ans;
    }

    private void helper(List<String> ans , int left, int right, int n, String s){
        if(left==n && right == n){
            ans.add(s);
            return;
        }
        if(left<n){
            helper(ans, left+1, right, n, s+'(');
        }
        if(left>right){
            helper(ans, left, right+1, n, s+')');
        }
    }
}

以下这六道题都有类似的结构，前一道是不含duplicate，后一道是含duplicate，含duplicate的需要进行sort。

39与40题是类似题目，也都是很显而易见的backtracking。这里我们要注意到，对于同一层的recursive，下面会有很多种可能的situation，这里面会包含有不合法的situation，比如40题中的[1 1 6 7]会产生两个[1 7]。这种时候要格外小心，比如40题我们并不是所有candidate[i]==candiate[i-1]的情况都不要(if(i>0 && candidates[i]==candidates[i-1]))，如果这么写[1 1 6]就被排掉了；而是对于这一层的recursive，如果某个candidate不是第一次出现而且还和前面相等，那说明不要它
39. Combination Sum:

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<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> temp = new LinkedList<>();
        dfs(ans, temp, candidates, target, 0);
        return ans;
    }
    
    private void dfs(List<List<Integer>> ans ,List<Integer> l, int[] candidates, int target, int pos){
        if(target==0){
            ans.add(new LinkedList<>(l));
            return;
        }
        
        if(target<0){
            return;
        }
        
        for(int i = pos;i<=candidates.length-1;i++){
            l.add(candidates[i]);
            dfs(ans, l, candidates, target-candidates[i], i);
            l.remove(l.size()-1);
        }
    }
}
  1. Combination Sum II:
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
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> temp = new LinkedList<>();
        dfs(ans, temp, candidates, target, 0);
        return ans;
    }
    
    private void dfs(List<List<Integer>> ans ,List<Integer> l, int[] candidates, int target, int pos){
        if(target==0){
            ans.add(new LinkedList<>(l));
            return;
        }
        
        if(target<0){
            return;
        }
        
        for(int i = pos;i<=candidates.length-1;i++){
            if(i>pos && candidates[i]==candidates[i-1])//不是这次recursive第一次出现且与前面的数相同的，我们不要
                continue;
            l.add(candidates[i]);
            dfs(ans, l, candidates, target-candidates[i], i+1);
            l.remove(l.size()-1);
        }
    }
}

46与47类似于39与40，47的条件也需要好好思考：到底哪些situation会进入到下一层的recursive，哪些是重复情况不能进入下一层的recursive。
46. Permutations:

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        boolean[] visited = new boolean[nums.length];
        List<Integer> l = new LinkedList<>();
        dfs(ans, l, nums, visited);
        return ans;
    }
    
    private void dfs(List<List<Integer>> ans, List<Integer> l, int[] nums, boolean[] visited){
        if(l.size()==nums.length){
            ans.add(new LinkedList<>(l));
            return;
        }
        
        for(int i =0;i<=nums.length-1;i++){
            if(visited[i]==false){
                visited[i] = true;
                l.add(nums[i]);
                dfs(ans, l, nums, visited);
                visited[i] = false;
                l.remove(l.size()-1);
            }
        }
    }
}

  1. Permutations II:

    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
    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ans = new LinkedList<>();
            boolean[] visited = new boolean[nums.length];
            List<Integer> l = new LinkedList<>();
            dfs(ans, l, nums, visited);
            return ans;
        }
        
        private void dfs(List<List<Integer>> ans, List<Integer> l, int[] nums, boolean[] visited){
            if(l.size()==nums.length){
                ans.add(new LinkedList<>(l));
                return;
            }
            
            for(int i =0;i<=nums.length-1;i++){
                if(visited[i]==false){
                    if(i>0 && nums[i]==nums[i-1] && visited[i-1]==true)//条件很关键，要好好想想
                        continue;
                    visited[i] = true;
                    l.add(nums[i]);
                    dfs(ans, l, nums, visited);
                    visited[i] = false;
                    l.remove(l.size()-1);
                }
            }
        }
    }

  2. Subsets:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ans = new LinkedList<>();
            List<Integer> l = new LinkedList<>();
            dfs(ans, l, nums, 0);
            return ans;
        }
        
        private void dfs(List<List<Integer>> ans, List<Integer> l, int[] nums, int pos){

            ans.add(new LinkedList<>(l));
            for(int i = pos;i<=nums.length-1;i++){
                l.add(nums[i]);
                dfs(ans, l, nums, i+1);
                l.remove(l.size()-1);
            }
        }
    }

  3. Subsets II:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ans = new LinkedList<>();
            List<Integer> l = new LinkedList<>();
            dfs(ans, l, nums, 0);
            return ans;
        }
        
        private void dfs(List<List<Integer>> ans, List<Integer> l, int[] nums, int pos){

            ans.add(new LinkedList<>(l));
            for(int i = pos;i<=nums.length-1;i++){
                if(i>pos && nums[i]==nums[i-1])
                    continue;
                l.add(nums[i]);
                dfs(ans, l, nums, i+1);
                l.remove(l.size()-1);
            }
        }
    }
  1. Sudoku Solver：这道题和上面的backtracking有些许不同，原因是它不需要返回而是直接在原来的board中修改。我们之前的backtracking的思路都是在这一层的recursive进行修改，进行下面的dfs，完成后把这一层恢复原状。这道题如果还是直接恢复原状的话会相当于什么都不做，所以我们的dfs带有boolean的返回值：如果我们成功所有下层的dfs都解决了，那么我们不需要恢复，否则的话还是恢复。
    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
    class Solution {
        public void solveSudoku(char[][] board) {
            solve(board, 0, 0);
        }
        
        private boolean solve(char[][] board, int i, int j){
            if(i==8 && j==9){
                return true;
            }
            if(j==9){
                i++;
                j = 0;
            }
            if(board[i][j]!='.'){
                return solve(board, i, j+1);
            }
            else{
                 for(int num = 1;num<=9;num++){
                    char c = (char)(num+'0');
                    if(valid(board, i, j, c)){
                        board[i][j] = c;
                        if(solve(board, i, j+1)){
                            return true;
                        }else{
                            board[i][j] = '.';                       
                        }
                    }

                }  
                return false;
            }

        }
        
        private boolean valid(char[][] board, int row ,int column, char c){
            for(int i =0;i<=board.length-1;i++){
                if(board[i][column]==c||board[row][i]==c){
                    return false;
                }
            }
            
            int x = row/3*3;
            int y = column/3*3;
            for(int i =x;i<=x+2;i++){
                for(int j=y;j<=y+2;j++){
                    if(board[i][j]==c){
                        return false;
                    }
                }
            }
            
            return true;
        }
        
    }
Follow

Catalogue

×