Subsets, Combination和Permutation（续）

90. Subsets II

这道题和78. Subsets稍有不同的地方是：这里的输入的数据中可能有duplicates。去重的方法就是：先把数据排序，然后每一步加的时候只加不同的数（如果nums[i]和nums[i-1]相同，就跳过），这样就保证了搜索树的每一个分支不同，也就保证了最后加到res里的每一个subset都不同。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null)
            return res;
        Arrays.sort(nums);
        backtrack(res, new ArrayList<Integer>(), 0, nums);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> l, int first_index, int[] nums){
        res.add(new ArrayList<>(l));
        int i = first_index;
        while (i < nums.length){
            if (i == first_index || nums[i] != nums[i-1]){
                l.add(nums[i]);
                backtrack(res, l, i+1, nums);
                l.remove(l.size()-1);
            }
            i++;
        }
    }
}

40. Combination Sum II

发现一个套路：

• 如果不包含duplicate，那么只用index不回头向前就能避免duplicate
• 如果包含duplicate，那么通常需要:
  1. sort数组
  2. 每次加数时只加不同的数，相同的数跳过
  3. index不回头向前

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0 || target <= 0)
            return res;
        Arrays.sort(candidates);
        backtrack(res, new ArrayList<>(), 0, candidates, 0, target);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> l, int sum, int[] cands, int first_index, int target){
        if (sum > target){
            return;
        }
        if (sum == target){
            res.add(new ArrayList<>(l));
            return;
        }
        int i = first_index;
        while (i < cands.length){
            if (i == first_index || cands[i] != cands[i-1]){
                l.add(cands[i]);
                sum += cands[i];
                backtrack(res, l, sum, cands, i+1, target);
                sum -= cands[i];
                l.remove(l.size()-1);
            }
            i++;
        }
    }
}

216. Combination Sum III

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || k > 9)
            return res;
        backtrack(res, new ArrayList<Integer>(), 0, k, n, 1);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> l, int sum, int k, int n, int first_num){
        if (l.size() == k && sum == n){
            res.add(new ArrayList<>(l));
            return;
        }
        if (l.size() == k || sum > n)
            return;
        for (int i = first_num; i < 10; i++){
            l.add(i);
            backtrack(res, l, sum+i, k, n, i+1);
            l.remove(l.size()-1);
        }
    }
}

377. Combination Sum IV

这道题比较有意思。也是包含duplicates，但是不能再无脑backtrack了。。。因为会TLE。。。主要原因是这道题把sequence不同的combination算成了不同的解（所以为什么还要叫combination sum。。。）。

所以就要想办法用HashMap存结果，或者用dp来做。

先考虑用HashMap存结果：

class Solution {
    static HashMap<Integer, Integer> mem;
    public int combinationSum4(int[] nums, int target) {
        if (target <= 0 || nums == null || nums.length == 0)
            return 0;
        mem = new HashMap<>();
        return dfs(nums, target);
    }

    public int dfs(int[] nums, int target){
        if (target < 0)
            return 0;
        if (target == 0)
            return 1;
        if (mem.containsKey(target))
            return mem.get(target);
        int ways = 0;
        for (int num : nums)
            ways += dfs(nums, target-num);
        mem.put(target, ways);
        return ways;
    }
}

再考虑dp的解法。这道题其实用dp来做比较合适，也没那么难想：可以把问题想象成climb stairs问题，每次走的台阶数是nums里的任何一个数，看最后爬上target个台阶的方法有多少。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0)
            return 0;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++){
            for (int num : nums){  // 遍历last step可能的走法
                if (i >= num){  // 最后达到的位置要 > last step
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    } 
}