阅读量:1
文章目录
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); } } } 