39. Combination Sum

Problem:

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

The same repeated number may be chosen from candidates 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]
]

Solution:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if(candidates == null || candidates.length == 0) return ans;
    List<Integer> list = new ArrayList<>();
    dfs(candidates, ans, list, target, 0,0);
    return ans;
        
}
public void dfs(int[] candidates, List<List<Integer>> ans, List<Integer> list, int target, int sum, int index){
    if(sum > target || index >= candidates.length) return;
        
    if(sum == target){
        ans.add(new ArrayList<>(list));
        return;
    }
    for(int i = index; i < candidates.length; i++){         
        list.add(candidates[i]);
        dfs(candidates, ans, list, target, sum + candidates[i], i);
        list.remove(list.size() - 1);
    }
}