Combination Sum

---

Combination Sum: 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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

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 2:

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

---

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

---

Try this Problem on your own or check similar problems:

1. Permutations
2. Combinations
3. Combination Sum II
4. Combination Sum II

Solution:

Java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }

    private void helper(int[] candidates, int currentSum, int target, List<Integer> currentList, List<List<Integer>> result){
        if(currentSum == target){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = 0; i < candidates.length; ++i){
            if(target >= currentSum + candidates[i] && (currentList.isEmpty() || candidates[i] >= currentList.get(currentList.size() - 1))){
                currentList.add(candidates[i]);
                helper(candidates, currentSum + candidates[i], target, currentList, result);
                currentList.remove(currentList.size() - 1);
            }
        }
    }
}

JavaScript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  const result = [];
  candidates.sort((a, b) => a - b);
  helper(candidates, 0, target, [], result);
  return result;
};
function helper(candidates, currentSum, target, currentList, result) {
  if (currentSum === target) {
    result.push(currentList.slice());
    return;
  }
  for (let i = 0; i < candidates.length; ++i) {
    if (
      target >= currentSum + candidates[i] &&
      (currentList.length === 0 ||
        candidates[i] >= currentList[currentList.length - 1])
    ) {
      currentList.push(candidates[i]);
      helper(
        candidates,
        currentSum + candidates[i],
        target,
        currentList,
        result
      );
      currentList.pop();
    }
  }
}

Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.helper(candidates, 0, target, [], result)
        return result

    def helper(self, candidates: List[int], currentSum: int, target: int, currentList: List[int], result: List[List[int]]) -> None:
        if currentSum == target:
            result.append(currentList[:])
            return
        for i in range(len(candidates)):
            if target >= currentSum + candidates[i] and (not currentList or candidates[i] >= currentList[-1]):
                currentList.append(candidates[i])
                self.helper(candidates, currentSum + candidates[i], target, currentList, result)
                currentList.pop()

C++

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        helper(candidates, 0, target, {}, result);
        return result;
    }
private:
    void helper(const vector<int>& candidates, int currentSum, int target, vector<int> currentList, vector<vector<int>>& result) {
        if (currentSum == target) {
            result.push_back(currentList);
            return;
        }
        for (int i = 0; i < candidates.size(); ++i) {
            if (target >= currentSum + candidates[i] && (currentList.empty() || candidates[i] >= currentList.back())) {
                currentList.push_back(candidates[i]);
                helper(candidates, currentSum + candidates[i], target, currentList, result);
                currentList.pop_back();
            }
        }
    }
};

---

Time/Space Complexity:

• Time Complexity: O(k*2^target)
• Space Complexity: O(k)

---

Explanation:

Another problem in the backtracking series. This time we're given candidates list and we're generating all combinations from that list that add up to target. Code is pretty similar to Combinations, but since we're looping over same elements again in the recursive calls the duplicates will occur. To cope with that we sort the array as we did Permutations II, and only go to recursive call if the sequence is ever increasing, so we won't have situation like (2,2,3) and (3,2,2) (remember combinations are unordered). helper takes the following parameters:

• candidates: Candidates Array
• currentSum: The sum of the numbers in the current combination
• target: Target Sum
• currentList: Current Combination
• result: Result containing all combinations that fulfill the requirement (add up to target)

The helper() function first checks if the current combination has reached the desired sum target. If it has, then we add a copy of the current combination to the result list.

If the current combination is not the desired sum, the function loops through the elements in the candidates’ array, adding each element to the current combination if it does not cause the sum to exceed the target, and if the element is greater than or equal to the last element in the current combination (to avoid generating duplicate combinations). Then, the function calls itself recursively with an updated currentSum, currentList, and result.

Once the recursive call returns, the function removes the last element from the current combination, to backtrack and try the next element in the next recursive call.

Once all recursive calls have returned, the function returns, and the original caller gets the result list of all found combinations.

Time complexity is O(k*2^target) where k is the average length of combinations we have generated. Since the worst-case scenario would be to have number 1 and to have up to target decisions (since we can repeat number 1 target number of times), so that's our depth of recursion tree and as for the width we our making the decisions to choose or not to choose the candidate, so we have 2 options. Also, we must not forget the multiplier k since we're copying the list. For the space complexity we will have just the average length of our combinations represented by currentList which we defined as k leading to O(k) space complexity.