Combination Sum

Given asetof candidate numbers (candidates)(without duplicates)and a target number (target), find all unique combinations incandidates where the candidate numbers sums totarget.

Thesamerepeated number may be chosen fromcandidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.

• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Analysis

Solution

Backtracking

这里技巧在于每次candidates的搜索空间要减小一些，但是又因为candidates[]元素可以重复利用，因此进入下一层递归时，用startIdx = i，而不是 startIdx = i + 1。

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

        Arrays.sort(candidates);

        helper(target, 0, 0, candidates, new ArrayList<>(), ans);

        return ans;
    }

    private void helper(int target, int sum, int startIdx, int[] candidates, 
                        List<Integer> combo, List<List<Integer>> ans) {
        if (sum == target) {
            ans.add(new ArrayList<Integer>(combo));
            return;
        }
        if (sum > target) {
            return;
        }

        for (int i = startIdx; i < candidates.length; i++) {
            combo.add(candidates[i]);
            // the startIdx is not i + 1 since we can reuse same elements
            helper(target, sum + candidates[i], i, candidates, combo, ans);
            combo.remove(combo.size() - 1);
        }
    }
}