Subsets & Combinations & Combination Sum

Subsets

Backtracking 不变的经典啊。

唯一注意的地方是，start == nums.length 的时候其实也是要添加结果的，不然会错。写回溯的时候，base case 要想清楚。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        dfs(rst, new ArrayList<>(), nums, 0);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int[] nums, int start){
        //if(start > nums.length) return;

        rst.add(new ArrayList<Integer>(list));

        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);

            dfs(rst, list, nums, i + 1);

            list.remove(list.size() - 1);
        }
    }
}

Subsets II

有重复元素也不难，先 sort，然后每一步上注意同样的元素别重复加一遍就好了。

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        Arrays.sort(nums);

        dfs(rst, new ArrayList<>(), nums, 0);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int[] nums, int start){
        rst.add(new ArrayList<Integer>(list));

        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);

            dfs(rst, list, nums, i + 1);

            list.remove(list.size() - 1);

            while(i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
        }
    }
}

Combinations

这类题的搜索树都是极度向左倾斜的结构，节点数为 2^n;

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> rst = new ArrayList<>();

        dfs(rst, new ArrayList<Integer>(), n, k, 1);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int n, int k, int cur){
        if(k == 0){
            rst.add(new ArrayList<>(list));
            return;
        }

        for(int i = cur; i <= n; i++){
            list.add(i);

            dfs(rst, list, n, k - 1, i + 1);

            list.remove(list.size() - 1);
        }
    }
}

Combination Sum

为什么觉得我好像在这 gitbook 里写过这题。。

• 元素可以重复选用，传进去的 index 可以以 i 为准。

• 但是还是不能走回头路，不然会有重复答案。

• 所有元素为正整数非常重要，要么这题可能有无数个解。

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> rst = new ArrayList<>();

        dfs(rst, new ArrayList<>(), candidates, target, 0, 0);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int[] nums, int target, int sum, int start){
        if(sum > target) return;
        if(sum == target){
            rst.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);

            dfs(rst, list, nums, target, sum + nums[i], i);

            list.remove(list.size() - 1);
        }
    }
}

Combination Sum II

• 没重复元素，想避免重复解，用 index 单调向前；

• 有重复元素，想避免重复解，index 之外每轮 dfs 末尾直接把指针移到下一个新元素上，一个元素在一轮 for loop 里只加一次。

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> rst = new ArrayList<>();

        Arrays.sort(candidates);
        dfs(rst, new ArrayList<>(), candidates, target, 0, 0);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int[] nums, int target, int sum, int start){
        if(sum > target) return;
        if(sum == target){
            rst.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);

            dfs(rst, list, nums, target, sum + nums[i], i + 1);

            list.remove(list.size() - 1);
            while(i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
        }
    }
}

Combination Sum III

Trivial problem.

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> rst = new ArrayList<>();

        dfs(rst, new ArrayList<>(), n, k, 0, 1);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, List<Integer> list, int target, int k, int sum, int start){
        if(sum > target || k < 0) return;
        if(sum == target && k == 0){
            rst.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = start; i <= 9; i++){
            list.add(i);

            dfs(rst, list, target, k - 1, sum + i, i + 1);

            list.remove(list.size() - 1);
        }
    }
}

Combination Sum IV

题目换成这样了之后依然是一个搜索问题，但是有了新的有趣特性。

主要在于这题和之前的 combination sum 还不太一样，它把 [1,3] 和 [3,1] 这种重复搜索算成两个解。于是强行制造了 overlap subproblems.

于是这题用搜索解会 TLE，加个 hashmap 做记忆化搜索，立刻就过了。

24ms ，时间复杂度较高，不如下面那个迭代的写法速度快。

O(n^d)，d代表得到 >= target 的搜索深度。

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        return dfs(nums, 0, target, new HashMap<Integer, Integer>());
    }

    private int dfs(int[] nums, int curSum, int target, HashMap<Integer, Integer> map){
        if(curSum > target) return 0;
        if(curSum == target) return 1;

        if(map.containsKey(curSum)) return map.get(curSum);

        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += dfs(nums, curSum + nums[i], target, map);
        }

        map.put(curSum, count);
        return count;
    }
}

论坛里还有比较有趣的迭代写法，只需要 3ms，原理和 climbing stairs 差不多，建一个大小等于 target + 1 的 array 代表多少种不同的方式跳上来，依次遍历即可。

时间复杂度 O(n * target) + O(n log n)

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] res = new int[target + 1];
        for (int i = 1; i < res.length; i++) {
        for (int num : nums) {
            if (num > i)
            break;
        else if (num == i)
            res[i] += 1;
        else
            res[i] += res[i-num];
        }
    }
        return res[target];
    }
}

原理和 climbing stairs 差不多，建一个大小等于 target + 1 的 array 代表多少种不同的方式跳上来，依次遍历即可。

时间复杂度 O(n * target)

注意这里内外循环的顺序不能错，要先按 sum 从小到大的顺序看，然后才是遍历每个元素。因为所谓 bottom-up，是相对于 sum 而言的，不是相对于已有元素的 index 而言的。

可以看到，在只取 min/max 的时候我们不同的循环顺序都能保证正确答案；但是求解的数量时，要以 target value 为外循环。

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[sum] = number of ways to get sum 
        int[] dp = new int[target + 1];

        // initialize, one way to get 0 sum with 0 coins
        dp[0] = 1;

        for(int j = 1; j <= target; j++){
            for(int i = 0; i < nums.length; i++){
                if(j - nums[i] >= 0) dp[j] += dp[j - nums[i]]; 
            }
        }

        return dp[target];
    }
}