【LeetCode】十四、回溯法：括号生成 + 子集

1、回溯法

使用场景，如找[1，2，3]的所有子集：

2、leetcode22：括号生成

以n=2为例，即两个左括号、两个右括号，枚举所有的情况：

从左往右数，当左括号的数量 < 右括号的数量时，就不是一个有效的括号，比如：

//一开始数到第一个就出现左括号的数量 < 右括号的数量
)()(
// 数到第三个时，左括号的数量 < 右括号的数量，无效
())(

如此，枚举所有可能性的过程中，如果出现左括号的数量 < 右括号的数量，则说明此路不通，终止递归，回溯到上一步重新选择

public class P22 {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backTracking(n, result, 0, 0, "");return result;}/**** @param n 需要的括号的数量* @param result 存结果，有合适的结果就塞进result* @param left 左括号的数量* @param right 右括号的数量* @param str 左右括号的分隔符，比如” “*/public static void backTracking(int n, List<String> result, int left, int right, String str) {// 右括号的数量大于左括号的数量了，说明是无效括号，此路不通，终止递归if (right > left){return;}// 左括号的数量等于右括号的数量，等于要求的数量，说明找到结果了，加入结果集，终止递归if (left == right && right == n){result.add(str);return;}// 左括号的数量小于要求的，可以加个左括号if (left < n) {backTracking(n, result, left + 1, right, str + "(");}// 右括号的数量小于要求的，可以加个右括号if (right < n) {backTracking(n, result, left, right + 1, str + ")");}}
}

3、leetcode78：子集

解法一：扩展法

以空集开始，遍历给定集合的每个元素，并把上面每一层的结果和当前元素相加。比如给定[1，2，3]

比如上面，遍历到3时，把3并入到前面三层的结果集：

第一层结果：[]
第二层结果：[1]
第三层结果：[2]  [1,2]

就得到了第四层：[3] 、[1，3]、 [2，3] 、[1，2，3]。代码实现：

public class P78 {public static List<List<Integer>> subsets(int[] nums) {if (nums == null) {return null;}List<List<Integer>> result = new ArrayList<>();// 空集这个子集result.add(new ArrayList<>());for (int num : nums) {List<List<Integer>> temp = new ArrayList<>();for (List<Integer> element : result) {// 不能直接修改element，否则会改变结果集的元素// 用一个同类型的对象，拷贝一份，防止发生引用传递List<Integer> copy = new ArrayList<>(element);// 将给定数组的一个个元素，并入结果集的每个元素copy.add(num);// 存入临时结果集，别放入最终结果集，这样result一直变，循环就停不下了temp.add(copy);}// 一层遍历完了，把结果放进最终的结果集，准备将给定数组的下一个元素分别并入结果集，得到新的子集temp.stream().forEach(e -> result.add(e));}return result;}
}

以上注意：遍历前面的结果集里的每个元素时，用一个copy对象，防止引用传递。测试结果与分析时所画的顺序也一致：

解法二：回溯法

以[1，2，3]为例，思路：

• 其子集的长度可能有：0、1、2、3
• 按这四种可能长度循环，每次找到符合长度的的子集，就放入结果集

public class P78 {public static List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList<>();// 长度为0的子集：空集，先放入result.add(new ArrayList<Integer>());// 子集长度还可能是1~给定的数组长度for (int i = 1; i <= nums.length; i++) {backTracking(nums, result, i, 0, new ArrayList<>());}return result;}public static void backTracking(int[] nums, List<List<Integer>> result, int length, int index, List<Integer> subset) {// 递归的终止条件：找到了满足长度的子集，加入结果集，停止递归if (subset.size() == length) {List<Integer> copy = new ArrayList<>(subset);result.add(copy);return;}for (int i = index; i < nums.length; i++) {subset.add(nums[i]);backTracking(nums, result, length, i+1, subset);// 找到了[1,2]，回溯，下一个该[1,3]了，这里remove掉2，以免下一个出现[1,2,3]subset.remove(subset.size() - 1);}}
}

解法三：DFS深度优先算法

public class P78 {public static List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList<>();dfs(nums, result, 0, new ArrayList<>());return result;}public static void dfs(int[] nums, List<List<Integer>> result, int index, List<Integer> subset) {List<Integer> copy = new ArrayList<>(subset);result.add(copy);if (index == nums.length) {return;}for (int i = index; i < nums.length; i++) {subset.add(nums[i]);dfs(nums, result, i+1, subset);subset.remove(subset.size() - 1);}}
}