39. Combination Sum

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.

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]
]

Related issue Subset, Subset II, Combination Sum II

question to ask :

• all positive number.
• will the set contains duplicates ?

backtracking.

about this line

        dfs(num, i, result, sum+num[i], target);

cause the question mention any number can be used many times, so next iteration will need to include this number again, which start from i.

BUT it can not start from 0(i.e. replace i with 0), why ? cause this will cause duplicates,

[2,3,6,7] target is 7, if you start from 0 again, will result in [2,2,3] & [2,3,2(start from 0 again)], which is duplicate.

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

        List<Integer> list = new ArrayList<>();
        Arrays.sort(num);
        dfs(num, 0, list, 0, target);

        return res;
    }

    private void dfs(int[] num, int start, List<Integer>result, int sum, int target){
        if(sum == target){
            res.add(new ArrayList<Integer>(result));
            return;
        }
        for(int i=start; i < num.length;i++){
            if(i > start && num[i] == num[i-1]) continue; // if the set doesn't contains duplicates, then this line won't be needed.
            if(num[i] + sum > target) break ;

            result.add(num[i]);
            dfs(num, i, result, sum+num[i], target);
            result.remove(result.size() -1);
        }

    }
}