【算法】回溯法四步走 (7)

生成一个\(2^n\)长的数组，数组的值从\(0\)到\(2^{n}-1\)。我们可以把它想象成为一颗二叉树，每个节点的子树都是一个不选0、一个选1

注意：我这里说的是 先不选0、再选1（即 01，先0后1），这样做的好处就是，我们不需要选了之后还原现场到不选的时候。

所以我们也可以参照这种方式来写，代码如下

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); helper(res, nums, new ArrayList<>(), 0); return res; } private void helper(List<List<Integer>> res, int[] nums, List<Integer> list, int index) { // 终止条件判断 if (index == nums.length) { res.add(new ArrayList<>(list)); return; } // 每一个节点都有两个分支，一个选一个不选 // 走不选这个分支，下一个 helper(res, nums, list, index + 1); // 不选，直接下一个 // 走选择这个分支 list.add(nums[index]); // 选择 helper(res, nums, list, index + 1); // 下一个 // 撤销选择 list.remove(list.size() - 1); } 以 start 表示范围区间

一般我们使用这种方法来表示不断前进的选择，即 本次选择不会考虑左边之前的选择，从start右边开始选。

相当于我们使用start把数组划分为了两个部分，第一个部分就是我们已经选择好的元素，第二部分就是我们还未选择的元素，我们需要做的就是从start开始将还未选择的元素放入左边已选择的元素中(start + 1)。

好处：这样我们可以省去用于存储数组访问情况的used[]数组，因为我们已选择和未选择已经分开了。

class Solution { List<List<Integer>> res = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { f(nums, 0); return res; } // 回溯法，从start开始选择 public void f(int[] nums, int start) { // if (start >= nums.length - 1) { res.add(new ArrayList<>(list)); // } // 从start开始选择 for (int i = start; i < nums.length; i++) { list.add(nums[i]); f(nums, i + 1); list.remove(list.size() - 1); } } } 以 [x][y] 表示完整的当前状态

本题完整的当前状态不需要参数即可。

如果小伙伴们想看此种情况的示例，可以看看剑指 Offer 13. 机器人的运动范围

优化思路 标识遍历过的元素

我们有两种方法可以来标识遍历过的元素，避免重复遍历。

修改元素数据为特定值（如 -1，Integer.MAX_VALUE），代表已经遍历过；

可以额外使用boolean[][] used;来存储遍历过的元素，遍历过就置为true。

剪枝 标志位flag

1.回溯算法可以设置标志位代表找到了，找到了就返回，避免继续回溯浪费时间；

if (flag) { return; } this.flag = true; 方法返回boolean

2.或者说找到了之后我们的方法就返回true，只要有一个true那就代表找到了，所以我们返回使用逻辑或recur(a) || recur(b)；
当然，还有一种情况就是，不符合条件我们就返回false，只要有一个false就代表不符合了，所以我们返回使用逻辑与recur(a) && recur(b)。

boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);` return res;

具体剪枝实例可以看下面的《剑指 Offer 12. 矩阵中的路径》

注意：这里可以看到，和我们上面明确函数功能所说的“返回数据”，即 返回数据应该是我们遇到递归出口之后，需要告诉给前一步递归的信息数据！对应上了。
我们需要把这一步找到了或者没找到的boolean信息传递给前一步递归，所以返回类型为boolean。

练习

下面提供一些我做过的「回溯」算法的问题，以便大家学习和理解「回溯」算法。

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

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

46. 全排列（中等） 47. 全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复； 39. 组合总和（中等） 40. 组合总和 II（中等） 77. 组合（中等） 78. 子集（中等） 90. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题； 60. 第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点； 93. 复原 IP 地址（中等） 题型二：Flood Fill