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);
}
}
}