39. Combination Sum

Description

Given a set of candidate numbers (C) (without duplicates) 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.
• 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]
]

Solution

Backtracking

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        if (candidates == null || candidates.length < 1) return combinations;
        
        Arrays.sort(candidates);
        List<Integer> combination = new ArrayList<>();
        combinationSumRecur(candidates, 0, target, combination, combinations);
        return combinations;
    }
    
    public void combinationSumRecur(int[] candidates,
                                   int begin,
                                   int target,
                                   List<Integer> combination,
                                   List<List<Integer>> combinations) {
        // important to judge this first, because begin could be out of range
        if (target == 0) { 
            combinations.add(new ArrayList<>(combination));
            return;
        }
        
        if (begin >= candidates.length || target < 0) {
            return;
        }
        
        combinationSumRecur(candidates, begin + 1, target, combination, combinations);
        int k = 0;
        while (candidates[begin] <= target) {
            combination.add(candidates[begin]);
            target -= candidates[begin];
            combinationSumRecur(candidates, begin + 1, target, combination, combinations);
            ++k;
        }
        
        while(k-- > 0) {
            combination.remove(combination.size() - 1);
        }
    }
}`