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