4.1 回溯算法解决子集、组合、排列问题

4.1.1 子集

• 输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集
• 比如说输入nums = [1,2,3]，应该输出8个子集，包括空集及其本身
• 第一个解法是利用数学归纳法的思想:假设现在已经知道了规模更小的子问题的结果，如何推到出当前问题的结果?
• 具体来说就是将nums = [1,2,3]拆分，如果已经知道了[1,2]的子集 ，是否可以推到出[1,2,3]的子集呢?具体地会发现这样一个规律:[1,2,3]的子集就是把[1,2]的子集中的每个集合在添加上3

subset([1,2,3])
= A+ [A[i].add(3) for i = 1...len(A)]
1
2

• 这就是一个典型的递归结构问题，[1,2,3]的子集可以由[1,2]追加得到，[1,2]的子集可以由[1]追加得出,那么base-case就是当输入集合为空的时候，输出子集也就是一个空集

vector<vector<int> > subsets(vector<int>& nums){
    //base-case,返回一个空集
    if(nums.empty()){
        return {{}};
    }
    //把最后一个元素拿出来
    int n = nums.back();
    nums.pop_back();
    //先递归算出前面元素的所有子集
    vector<vector<int>> res =  subsets(nums);
    int size = res.size();
    for(int i = 0;i<size;i++){
        //然后在之前的结果之上累加
        res.push_back(res[i]);
        res.back().push_back(n);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    private List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums.length-1,nums);
        return ans;
    }
    private List<Integer> copy(List<Integer> raw,int n){
        List<Integer> newList = new ArrayList<>();
        for (Integer id : raw) {
            newList.add(id);
        }
        newList.add(n);
        return newList;
    }
    //递归计算
    private void dfs(int cur,int[] nums){
        if(cur == -1){
            //此时为空集
            ans.add(new ArrayList<>());
            return;
        }
        //先计算出之前所有元素的子集
        int n = nums[cur];
        dfs(cur-1,nums);
        //然后在先前的基础上追加即可
        int size = ans.size();
        for(int i = 0;i<size;i++){
            List<Integer> copy = copy(ans.get(i), n);
            ans.add(copy);
        }
    }
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

• 来分析一下这个问题的时间复杂度，计算递归算法的时间复杂度方法是，找到递归的深度然后乘以每次递归中的迭代的次数，对于这个问题而言，递归的问题是N，但是我们发现每次递归for循环的迭代次数取决于res的长度，这并不是固定的

• 依照刚才的思路，res的长度应该是每次递归都会翻倍，所以说总的迭代次数应该是2^{N，这是因为一个大小为N的集合的自己总共会有2}N个，所以说res添加元素只有会有2^N，同时我们copy的时候，是把ans[i]复制一份添加到数组的最后，所以一次操作的时间是O(N)，还是比较耗时的

• 回溯算法解决该问题

result = []
def backtrack(路径,选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径,选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9

• 如果涉及到路径和选择，那么得要想办法将该问题中有限的所有可能都给列举出来，如何将所有自己都穷举出来呢?

• 我们手工分析一波

  • 首先base-case,空集[]是一个子集
  • 然后我们找以1开头的子集,[1]、[1,2]、[1,2,3]
  • 以2开头的子集,[2],[2,3]
  • 以3开头的子集,[3]

• 最终以上这些自己加起来就是[1,2,3]的所有子集

• 核心思路:用一个start参数控制递归，生成这样的一棵树，其实只要改造回溯算法的模板就可以了

    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> track = new ArrayList<>();
        backtrack(track,0,nums);
        return ans;
    }
    //backtrack(路径,选择列表)
    private void backtrack(List<Integer> list,int start,int[] nums){
        //前序遍历的位置
        ans.add(copy(list));
        //从start开始,避免产生重复的子集
        for(int i = start;i<nums.length;i++){
            //做选择
            list.add(nums[i]);
            //递归回溯
            backtrack(list,i+1,nums);
            //撤销选择
            list.remove(list.size()-1);
        }
    }
    private List<Integer> copy(List<Integer> raw){
        List<Integer> newList = new ArrayList<>(raw);
        return newList;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4.1.2 组合

• 输入两个数字n,k，算法输出[1...n]中k个数字的所有组合

• 手工分析样例combine(4,2)

  • 以1开头的，长度为2的组合[1,2],[1,3],[1,4]

  • 以2开头的:[2,3],[2,4]

  • 以3开头的[3,4]

• 这也是典型的回溯算法，k限制了树的高度，n限制了树的宽度

• 套用回溯算法模板，其实我们可以发现，这其实就是一种特殊的子集，只不过这个子集的长度被限制了，限制了只有k

    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        if(k<=0 || n<=0){
            return ans;
        }
        List<Integer> track = new ArrayList<>();
        backtrack(track,1,n,k);
        return ans;
    }

    private void backtrack(List<Integer> track,int start,int n,int k){
        if(track.size() == k){
            ans.add(new ArrayList<>(track));//copy简洁写法
            return;
        }
        for(int i = start;i<=n;i++){
            //做选择
            track.add(i);
            //递归回溯
            backtrack(track,i+1,n,k);
            //撤销选择
            track.remove(track.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

4.1.3 排列

• 输入一个不包含重复数字的数组nums，返回这些数字的全排列
• 通过上面两个问题的理解，排列这个集合，是所有子集的子集，但是不同于组合，组合没有顺序要求(意思是就算不同顺序，它也算一个)，但是排列的话就是有顺序要求的，不同顺序也算一个
• 那么如果要回溯的话，就需要手动来剔除那些不符合的排列

    private List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> permute(int[] nums) {
        List<Integer> track = new ArrayList<>();
        backtrack(track,nums);
        return ans;
    }
    
    //(路径,选择列表)
    private void backtrack(List<Integer> track,int[] nums){
        //到达叶子节点
        if(track.size() == nums.length){
            ans.add(new ArrayList<>(track));
        }
        //做选择
        for(int i = 0;i<nums.length;i++){
            if(track.contains(nums[i])){
                continue;
            }
            //做选择
            track.add(nums[i]);
            //回溯递归
            backtrack(track,nums);
            //撤销选择
            track.remove(track.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

4.2 回溯算法最佳实践:解数独

• 对于解数独而言，我们的手工实践也许是穷举:算法对每一个空着的格子穷举1到9，如果遇到不合法的数字(在同一行或者同一列或同一个3*3的区域中存在相同的数字)则跳过，如果找到一个合法的数字，则继续穷举下一个空格子就好了
• 输入是一个9*9的棋盘，其中有一些各自已经预先填入了数字，空白格子用点号字符.来表示，算法需要在原地修改棋盘，将空白格子填上数字，得到一个可行解

4.2.1 代码实现

• 根据前文的回溯算法，求解数独的思路很直接，就是对每一个格子的所有可能的数字进行穷举，对于每个位置，有1-9这些数字的旋转，这就是选择列表，路径就是棋盘上的数字分布情况(也就是状态)

• 基本代码框架

    private void backtrack(char[][] board,int i,int j){
        int m =9,n=9;
        if(j==n){
            //如果穷举到最后一列的话就换行就好了
            backtrack(board,i+1,0);
            return;
        }
        //如果该位置是预设的数字,则不需要我们去推导
        if(board[i][j]!='.'){
            backtrack(board,i,j+1);
            return;
        }
        for(char ch = '1';ch<='9';ch++){
            //判定该数字是否合法
            if(!isValid(board,i,j,ch)){
                continue;
            }
            //做选择
            board[i][j] = ch;
            //继续穷举下一个位置
            backtrack(board,i,j+1);
            //撤销选择
            board[i][j] = '.';
        }
    }
    private boolean isValid(char[][] board,int row,int col,char ch){
        for(int i =0;i<9;i++){
            //判断行是否存在重复
            if(board[row][i] == ch){
                return false;
            }
            //判断列是否存在重复
            if(board[i][col] == ch){
                return false;
            }
            //判断3*3之内是否存在重复
            if(board[(row/3)*3+i/3][(col/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
42

• 这个框架还缺少个递归结束条件，当r==m的时候就说明穷举完了最后一行，完成了所有的穷举，这就是base-case
• 为了减少复杂度，可以让backtrack的函数返回值为boolean，如果找到了一个可行解，就返回true,这样可以组织后续的递归

    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }

    private boolean backtrack(char[][] board,int i,int j){
        int m =9,n=9;
        if(i==m){
            //如果找到一个可行解,那么就触发base-case
            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(!isValid(board,i,j,ch)){
                continue;
            }
            //做选择
            board[i][j] = ch;
            //继续穷举下一个位置
            if(backtrack(board,i,j+1)){
                return true;
            }
            //撤销选择
            board[i][j] = '.';
        }
        return false;
    }
    private boolean isValid(char[][] board,int row,int col,char ch){
        for(int i =0;i<9;i++){
            //判断行是否存在重复
            if(board[row][i] == ch){
                return false;
            }
            //判断列是否存在重复
            if(board[i][col] == ch){
                return false;
            }
            //判断3*3之内是否存在重复
            if(board[(row/3)*3+i/3][(col/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
42
43
44
45
46
47
48
49
50
51

4.3 回溯算法最佳实践:括号生成

• 请你写一个算法，输入是一个正整数n，输出n对括号的所有合法组合

• 合法括号的性质

  • 一个合法括号组合的左括号数量一定等于右括号数量
  • 对于一个合法的括号字符串组合p，必然对于任何0<=i都有:子串p[0....i]中左括号的数量都大于等于右括号的数量

• 以回溯的角度来说，可以转换为如下问题，现在有2n个位置，每个位置可以放置字符(或者)，组成的所有括号组合中，有多少个是符合的?最直观的想法就是从全部2^(2n)种组合中，根据上面总结出来的合法括号组合的性质选出合法的组合

• 2^{(2n)计算方法，每个位置有两个选择，一共有2n个位置，那就2n个2相乘，总情况数是2}(2n)

    List<String> ans = new ArrayList<String>();
    public List<String> generateParenthesis(int n) {
        if(n==0){
            return ans;
        }
        StringBuilder track = new StringBuilder();
        backtrack(track,n,n);
        return ans;
    }

    //路径,选择列表,i是当前的位置,n是规定的括号列表长度
    private void backtrack(StringBuilder track,int left,int right){//可用的左括号数量为left个,可用的右括号数量为right个
        if(left<0 || right<0){
            return;
        }
        //如果左括号用得少,那么肯定不合法
        if(left>right){
            return;
        }
        //当所有括号都刚好用完的时候,那么就得到一个合法的组合了
        if(left ==0 && right ==0){
            ans.add(track.toString());
            return;
        }
        char[] choices= new char[]{'(',')'};
        for(int j = 0;j<choices.length;j++){
            //做选择
            track.append(choices[j]);
            //穷举下一个位置
            if(j== 0){
                backtrack(track,left-1,right);
            }
            if(j==1){
                backtrack(track,left,right-1);
            }
            //撤销选择
            track.deleteCharAt(track.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

vector<vector<int>> neighbor={
    {1,3},
    {0,4,2},
    {1,5},
    {0,4},
    {3,1,5}
    {4,5}
}
1
2
3
4
5
6
7
8

    public int slidingPuzzle(int[][] board) {
        //1.制作映射表
        int[][] neighbor = new int[6][];
        neighbor[0] = new int[]{1,3};
        neighbor[1] = new int[]{0,2,4};
        neighbor[2] = new int[]{1,5};
        neighbor[3] = new int[]{0,4};
        neighbor[4] = new int[]{1,3,5};
        neighbor[5] = new int[]{2,4};
        int m =2,n=3;
        StringBuilder start = new StringBuilder();
        StringBuilder target = new StringBuilder("123450");
        //将2X3的数组转化为字符串
        for(int i = 0;i<m;i++){
            for(int j =0;j<n;j++){
                start.append(board[i][j]);
            }
        }
        /*BFS搜索*/
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(start.toString());
        visited.add(start.toString());
        int step = 0;
        while(!q.isEmpty()){
            int sz = q.size();
            for(int i =0;i<sz;i++){
                String head = q.poll();
                if(head.equals(target.toString())){
                    return step;
                }
                //找到数字索引0
                int idx = 0;
                for(;head.toString().charAt(idx)!='0';idx++);
                //将数字0和响铃的数字交换位置
                for(int adj:neighbor[idx]){
                    StringBuilder newBoard = new StringBuilder(head);
                    char ch = newBoard.charAt(adj);
                    newBoard.setCharAt(adj,newBoard.charAt(idx));
                    newBoard.setCharAt(idx,ch);
                    //防止走回头路
                    if(!visited.contains(newBoard.toString())){
                        q.offer(newBoard.toString());
                        visited.add(newBoard.toString());
                    }
                }
            }
            step++;
        }
        return -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