【算法】回溯算法

发表于2021-11-22更新于2022-03-03字数统计4.2k阅读时长29分阅读次数

回溯算法简介

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

  • 找到一个可能存在的正确的答案；
  • 在尝试了所有可能的分步方法后宣告该问题没有答案。

回溯算法相关的典型题目：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

题型一：排列、组合、子集相关问题

提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。

题型二：Flood Fill

题型三：字符串中的回溯问题

题型四：游戏问题

排列系列问题

打印一个字符串的全部子序列

打印一个字符串的全部子序列，包括空字符串。

思路：

  • 递归过程中在修改 char[] 数组当前位置的值为空 ''，代表不考虑当前字符的情况，修改后进入子问题，得到不考虑当前位置字符时的结果；然后该子问题的方法栈调用完毕后，再将原始值赋值回去，再调用一次子问题，代表考虑当前字符的情况，又可以得到一种结果
  • 递归到底时，再保存当前 char[] 中的内容到结果列表里。
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
public static List<String> printAllSubsquences(String str) {
    if (str == null) {
        return null;
    }

    char[] cstr = str.toCharArray();
    List<String> res = new ArrayList<>();
    process(0, cstr, res);
    return res;
}

public static void process(int i, char[] cstr, List<String> res) {
    if (i == cstr.length) {
        // 到底了，将当前的 cstr 转成 String 并保存到 res 中
        res.add(new String(cstr));
        return;
    }

    // 分支一：不考虑当前位置
    char tmp = cstr[i];
    cstr[i] = 0;
    process(i + 1, cstr, res);

    // 分支二：考虑当前位置
    cstr[i] = tmp;
    process(i + 1, cstr, res);
}

public static void main(String[] args) {
    String test = "abc";
    System.out.println(printAllSubsquences(test));
}

打印一个字符串的全部排列

相似题目：【全排列】打印一个数组的全部排列

打印一个字符串的全部排列，要求不要出现重复的排列。

思路：本题使用交换字符的技巧减少占用的空间，并设置 visited[] 数组避免重复的排列（可能某些字符会重复出现在数组中）

代码：

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
public static List<String> printAllPermutations(String str) {
    if (str == null) {
        return null;
    }
    char[] cstr = str.toCharArray();
    List<String> res = new ArrayList<>();
    process(0, cstr, res);
    return res;
}

// 不重复体现在多一个 visited[] 数组
public static void process(int i, char[] cstr, List<String> res) {
    if (i == cstr.length) {
        // 到底时保存结果
        res.add(new String(cstr));
        return;
    }
    // 作用：在当前层遍历length-i种可能时，避免相同的字符都被swap到当前i位置，造成生成重复子序列
    boolean[] visited = new boolean[26];
    // 前i-1的字符顺序已定，当前层的字符可能有 length-i 种可能，每一种都对应了一个分支（子问题）
    // 通过swap的方式确定前i-1字符，做到节省空间
    for (int j = i; j < cstr.length; j++) {
        // 先判断当前位置的字符是否在当前层已经访问过了，能避免重复子序列
        if (visited[cstr[j] - 'a'] == true) {
            continue;
        }
        // 代表当前字符已经访问过了
        visited[cstr[j] - 'a'] = true;
        // 先将遍历到的当前字符交换到第i个位置（当前递归栈遍历到第i层）
        // 目的是保证遍历到第i层时，数组中的前i个元素是保存着当前分支下确定好顺序的字符，
        // 也就是当前分支下已经确定了前i个元素的顺序，后面的字符要在子问题里确认顺序
        swap(cstr, i, j);
        process(i + 1, cstr, res);
        // 当前分支处理完后记得交换回来，不要影响当前层的其他分支
        swap(cstr, i, j);
    }
}

private static void swap(char[] cstr, int i, int j) {
    char tmp = cstr[i];
    cstr[i] = cstr[j];
    cstr[j] = tmp;
}

public static void main(String[] args) {
    String test = "abc";
    System.out.println(printAllPermutations(test));
}

46. 全排列

46. 全排列：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

本问题和上一个问题非常相似。区别在于数组不重复，无需设置 visited 数组判断每个字符是否已经被交换过

代码：

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
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    permuteHelper(0, nums, res);
    return res;
}

public void permuteHelper(int i, int[] nums, List<List<Integer>> res) {
    if (i == nums.length) {
        // 到底了
        // 将当前nums（在前面的递归里已经被swap了顺序）加入到结果集合
        List<Integer> list = new ArrayList<>();
        for (int k = 0; k < nums.length; k++) {
            list.add(nums[k]);
        }

        res.add(list);
        return;
    }

    for (int j = i; j < nums.length; j++) {
        // 交换当前j和i，使得当前j的元素值处于i位置（当前递归处的首位置
        // 交换的目的是，为了打乱顺序，调整排列顺序，可以理解为将前i个元素给定好顺序（通过交换的手段令前面排好序，后面的length-i个元素的顺序将在其递归栈中通过swap决定顺序）
        swap(nums, i, j);
        // 当前已经有i个元素在确认区间内了，
        // 并且这i个元素均处于数组的前i个位置（交换了）
        // 该从第i+1个位置元素继续递归了          
        permuteHelper(i + 1, nums, res);
        swap(nums, i, j);
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

47. 全排列 II

47. 全排列 II：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

该问题和前面的打印一个字符串的全部排列非常相似，都需要使用 visited[] 数组判断是否重复

代码：

78. 子集

78. 子集：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

思路：当前位置的数字可以选择添加到子集，也可以选择不添加到子集。遍历所有情况即可得到所有子集。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List<List<Integer>> res;
public List<List<Integer>> subsets(int[] nums) {
    res = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    recur(nums, 0, set);
    return res;
}

public void recur(int[] nums, int i, Set<Integer> set) {
    if (i == nums.length) {
        // 添加到集合里
        res.add(new ArrayList<>(set));
        return;
    }

    recur(nums, i + 1, set);
    set.add(nums[i]);
    recur(nums, i + 1, set);
    set.remove(nums[i]);
}

90. 子集 II

90. 子集 II：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

与上一题的区别在于有重复元素。

策略：先排序。如果当前值等于前一个值。那么判断前一个值是否被选中

  • 如果被选中，则当前值可以被选中，也可以不被选中
  • 如果没被选中，则当前值不能被选中（因为这种情况会和第一种中的某一个情况重复，例如前选中，后没选中）

代码：

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
public List<List<Integer>> ans;
public List<List<Integer>> subsetsWithDup(int[] nums) {
    // 策略：先排序。如果当前值等于前一个值。那么判断前一个值是否被选中。
    // 如果被选中，则当前值可以被选中，也可以不被选中
    // 如果没被选中，则当前值不能被选中（因为这种情况会和第一种中的某一个情况重复，例如前选中，后没选中）
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }
    Arrays.sort(nums);
    ans = new ArrayList<>();
    List<Integer> selected = new ArrayList<>();
    recur(nums, 0, false, selected);
    return ans;
}

public void recur(int[] nums, int i, boolean preIsSelected, List<Integer> selected) {
    if (i == nums.length) {
        ans.add(new ArrayList<>(selected));
        return;
    }

    if (i > 0 && nums[i - 1] == nums[i] ) {
        if (preIsSelected) {
            // 前一个被选中，则当前可以选也可以不选
            selected.add(nums[i]);
            recur(nums, i + 1, true, selected);
            selected.remove(selected.size() - 1);
            recur(nums, i + 1, false, selected);
        } else {
            // 前一个没被选中，则当前不可以被选中
            recur(nums, i + 1, false, selected);
        }
    } else {
        // 不相等，就即可以选中，又可以不选中
        selected.add(nums[i]);
        recur(nums, i + 1, true, selected);
        selected.remove(selected.size() - 1);
        recur(nums, i + 1, false, selected);
    }
}

39. 组合总数

39. 组合总和：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

代码：

回溯算法常见题目

汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制：

  • 每次只能移动一个盘子
  • 盘子只能从柱子顶端滑出移到下一根柱子
  • 盘子只能叠在比它大的盘子上

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。你需要原地修改栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    // 用栈：先将所有元素start中的元素都压入到other中，然后start最底层的圆盘就可以压入到end里了
    // 递归进行该过程
    hanotaHelper(A.size(), A, C, B);
}

// A: start B: end C: Other
public void hanotaHelper(int i, List<Integer> start, List<Integer> end, List<Integer> other) {
    if (i == 1) {
        // base case
        end.add(0, start.remove(0));
        return;
    }
    // 把 i-1 个元素压入other中备用，i要到end中
    hanotaHelper(i-1, start, other, end);
    // i 从 start 到 end
    end.add(0, start.remove(0));
    // 再把other里备用的i-1个重新压入到end中
    hanotaHelper(i-1, other, end, start);
}

栈的逆序

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现?

思路：

定义方法 reverse()，将递归地调用该方法将整个栈中的元素进行反转，步骤：

  • 先调用自定义的方法 getAndRemoveLastElement() 抽取出栈底元素
  • 接着递归调用 reverse() 方法栈中剩余元素进行反转
  • 反转完毕后，再将刚才抽取出的栈底元素放到栈顶，即完成了整体的逆序

该过程利用了系统栈将每一层方法栈中抽取的栈底元素保存起来，将剩余元素逆序后再回到当前方法栈，取回刚才保存的栈底元素放到栈顶。

代码：

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
public static void reverse(Stack<Integer> stack) {
    if (stack.isEmpty()) {
        // base case
        return;
    }

    // 1. 取出栈底元素
    Integer tmp = getAndRemoveLastElement(stack);
    // 2. 剩余元素递归逆序
    reverse(stack);
    // 3. 栈底元素放到栈顶
    stack.push(tmp);
}

// 取出栈底元素并将其从栈中删除
// 可以形象的理解为：
// 1. 当前层的元素先弹出来，存到当前栈位置的局部变量表里
// 2. 一层一层调用时，栈不断减小，这些元素不断被弹出保存到局部变量表里
// 3. 直到最后一层，满足了base case，将栈底元素一路return到最外层的方法栈，
//    在这个过程中之前被保存到局部变量表里的变量不断再压入栈中，从而恢复了栈
public static Integer getAndRemoveLastElement(Stack<Integer> stack) {
    // 这里不需要判断栈是否为空，因为在调用该方法的reverse()方法里已经判断过了

    Integer cur = stack.pop();
    if (stack.isEmpty()) {
        // base case
        // 如果此时栈空了，说明刚才弹出的就是栈底元素
        return cur;
    } else {
        // 如果栈还不为空，说明还没找到栈底，则递归调用该方法继续寻找栈底，
        // 一直递归到栈底，在栈底时触发上面if成立的条件，从而将该元素一路返回到最外层递归，从而找到了栈底元素
        Integer last = getAndRemoveLastElement(stack);
        stack.push(cur);
        return last;
    }
}

public static void main(String[] args) {
    Stack<Integer> test = new Stack<Integer>();
    test.push(1);
    test.push(2);
    test.push(3);
    test.push(4);
    test.push(5);
    reverse(test);
    while (!test.isEmpty()) {
        System.out.println(test.pop());
    }
}

N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

代码：

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
class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 记录每一行的皇后存储在哪一列
        // 例如 record[2] = 3 代表第3行的皇后在第4列
        int[] record = new int[n];
        process(0, record, n);
        return res;
    }

    List<List<String>> res = new ArrayList<>();

    public void process(int i, int[] record, int n) {
        if (i == n) {
            // 在调用到底时才生成答案，这样就能保证答案一定正确
            res.add(generateBoard(n, record));
            return;
        }

        // j代表在第i行尝试的列数，需要尝试所有列的情况
        for (int j = 0; j < n; j++) {
            // 先检查第i行第j列能否放皇后（要根据前i-1行的皇后摆放情况来验证）
            if (isValid(record, i, j)) {
                // 如果第i行第j列可以摆放，则更新record数组
                record[i] = j;
                // 递归调用下一行
                process(i + 1, record, n);
            }
        }
    }

    public boolean isValid(int[] record, int i, int j) {
        // 遍历前i-1行的record
        for (int k = 0; k < i; k++) {
            if (record[k] == j || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

    public List<String> generateBoard(int n, int[] record) {
        List<String> list = new ArrayList<>();
        for (int row = 0; row < n; row++) {
            // record[row]存储着第k行的皇后位置，据此生成String
            // StringBuilder sb = new StringBuilder();
            // for (int col = 0; col < n; col++) {
            //     if (col == record[row]) {
            //         sb.append('Q');
            //     } else {
            //         sb.append('.');
            //     }
            // }
            // list.add(sb.toString());

            // 改进版：
            char[] board = new char[n];
            Arrays.fill(board, '.'); // 快速填充
            board[record[row]] = 'Q';
            list.add(new String(board));
        }
        return list;
    }
}