Combination Sum I & II

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. 

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

I was confused at first how to repeatedly use an element. Then I realized that it is just start point of the recursion is different: start from i if the element can be repeatedly used and from i + 1 if it cannot.

Btw, the reason to use "start" but not start from the beginning of the array each time is to get only one combination each time. For example, to remove (2, 3, 2) from the combinations.

Otherwise they are just normal backtracking. O(n!)

Combinations I

public List> combinationSum(int[] candidates, int target) {
        if (candidates == null)
            throw new NullPointerException("Null array!");
        List> rst = new ArrayList> ();
        if (candidates.length == 0)
            return rst;
        Arrays.sort(candidates);
        getCombinations(candidates, target, rst, new ArrayList (), 0);
        return rst;
    }
    private void getCombinations(int[] candidates, int target, List> rst, List combination, int start) {
        if (target < 0)
            return;
        if (target == 0) {
            rst.add(new ArrayList(combination));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target)
                break;
            if (i != start && candidates[i] == candidates[i - 1])
                continue;
            combination.add(candidates[i]);
            getCombinations(candidates, target - candidates[i], rst, combination, i);
            combination.remove(combination.size() - 1);
        }
    }

Combinations II

public List> combinationSum2(int[] num, int target) {
        if (num == null)
            throw new NullPointerException("Null array!");
        List> rst = new ArrayList> ();
        if (num.length == 0)
            return rst;
        Arrays.sort(num);
        getCombinations(num, target, rst, new ArrayList (), 0);
        return rst;
        
    }
    private void getCombinations(int[] num, int target, List> rst, List combination, int start) {
     if (target < 0)
            return;
        if (target == 0) {
            rst.add(new ArrayList(combination));
            return;
        }
        for (int i = start; i < num.length; i++) {
            if (num[i] > target)
                break;
            if (i != start && num[i] == num[i - 1])
                continue;
            combination.add(num[i]);
            getCombinations(num, target - num[i], rst, combination, i + 1);
            combination.remove(combination.size() - 1);
        }
    }