Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Examples

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output:[[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output:[[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

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 combinations themselves must be sorted in ascending order.
- CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1)
- The solution set must not contain duplicate combinations.

Warning : DO NOT USE LIBRARY FUNCTION FOR GENERATING COMBINATIONS. Example : itertools.combinations in python.

Solution

Method 1 - Backtracking

The first impression of this problem should be depth-first search(DFS). To solve DFS problem, recursion is a normal implementation.

Note that the candidates array is not sorted, we need to sort it first, if we need sorted output from the list.

Also, normal recursion decision tree may have issues. For e.g. for array [2,3,6,7], when we choose 2, it may have 3 later. So, when we come to number 3, we should make sure, that we don’t take 2 again, as that will result in duplicates.

So, we have to take 1 index and keep on adding it, till we find the solution.

Code

Java
Without using loop
public List<List<Integer>> combinationSum(int[] candidates, int target) {  
    List<List<Integer>> ans = new ArrayList<>();  
  
    if (candidates == null || candidates.length == 0) return ans;  
  
    Arrays.sort(candidates); // needed if only sorted output wanted  
  
    dfs(candidates, target, 0, 0, new ArrayList<Integer>(), ans);  
  
    return ans;  
}  
  
public void dfs(int[] candidates, int target, int idx, int currSum, List<Integer> subAns, List<List<Integer>> ans) {  
    // base case 1  
    if (target == currSum) {  
        ans.add(new ArrayList<>(subAns));  
        return;  
    }  
  
    // base case 2  
    if (idx >= candidates.length || currSum > target) {  
        return;  
    }  
  
    // take current candidate  
    // not idx + 1 because we can reuse same elements    
    subAns.add(candidates[idx]);  
    dfs(candidates, target, idx, currSum + candidates[idx], subAns, ans);  
    // dont take current candidate, currSum statys same  
    subAns.remove(subAns.size() - 1);  
    dfs(candidates, target, idx + 1, currSum, subAns, ans);  
}
Using the loop
public List<List<Integer>> combinationSum(int[] nums, int target) {  
    List<List<Integer>> ans = new ArrayList<>();  
    Arrays.sort(nums);  
    backtrack(nums, target, 0, new ArrayList<>(), ans);  
    return ans;  
}  
  
private void backtrack(int[] nums, int target, int idx, List<Integer> subAns, List<List<Integer>> ans) {  
    if (target < 0) {  
        return;  
    }  
    if (target == 0) {  
        ans.add(new ArrayList<>(subAns));  
        return;  
    }  
  
    for (int i = idx; i < nums.length; i++) {  
        subAns.add(nums[i]);  
        backtrack(nums, target - nums[i], i, subAns, ans); // not i + 1 because we can reuse same elements  
        subAns.remove(subAns.size() - 1);  
    }  
}