Combinations Continued

Combination Sum II, 跟Subsets II一模一样， 就是加了一个target sum的限制条件。这题也是需要先sort的，可以保证从小往大做加法。

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

        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<Integer>();
        dfs(result, list, candidates, target, 0, 0);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int[] candidates, int target, int pos, int current) {
        if (current == target) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        if (pos == candidates.length || current > target) {
            return;
        }

        for (int i = pos; i < candidates.length; i++) {
            if (i != pos && candidates[i] == candidates[i - 1]) {
                continue;
            }
            list.add(candidates[i]);
            dfs(result, list, candidates, target, i + 1, current + candidates[i]);
            list.remove(list.size() - 1);
        }
    }
}

Combination Sum III, 一样，限制条件是element的个数以及target sum.

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (k <= 0 || n <= 0) {
            return result;
        }
        int sum = 0;
        for (int i = 1; i <= 9; i++) {
            sum += i;
        }
        if (n > sum) {
            return result;
        }

        List<Integer> list = new ArrayList<Integer>();
        dfs(result, list, k, n, 1, 0);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int k, int n, int pos, int current) {
        if (list.size() == k && current == n) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        if (pos == 10 || list.size() > k || current > n) {
            return;
        }

        for (int i = pos; i <= 9; i++) {
            list.add(i);
            dfs(result, list, k, n, i + 1, current + i);
            list.remove(list.size() - 1);
        }
    }
}

Combination Sum IV

看到return type不是所有结果，而是所有结果的个数的时候，想一想这题是不是不是用搜索做的，而是用dp做的。

解法一：dfs + memorization = dp (top down)
仍然用dfs，用一个hashmap或者一个array去记录已经搜索过的值
注意set当值为0时，是有一个结果的

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target < 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1);
        return dfs(nums, target, map);
    }

    private int dfs(int[] nums, int target, Map<Integer, Integer> map) {
        if (map.containsKey(target)) {
            return map.get(target);
        }

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target < nums[i]) {
                continue;
            }
            sum += dfs(nums, target - nums[i], map);
        }
        map.put(target, sum);
        return sum;
    }
}

解法二：bottom up

public 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 j = 0; j < nums.length; j++) {
                if (nums[j] > i) {
                    continue;
                }
                dp[i] += dp[i - nums[j]];
            }
        }

        return dp[target];
    }
}

Factor Combinations, 在 n % i != 0时return，不然会超时。

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n < 2) {
            return result;
        }

        List<Integer> list = new ArrayList<Integer>();
        dfs(result, list, 2, n);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int pos, int n) {
        if (n == 1) {
            if (list.size() > 1) {
                result.add(new ArrayList<Integer>(list));
                return;                
            }
        }

        for (int i = pos; i <= n; i++) {
            if (n % i != 0) {
                continue;
            }
            list.add(i);
            dfs(result, list, i, n / i);
            list.remove(list.size() - 1);
        }
    }
}