Combination Sum

Problem Statement

In this challenge, you are given an array of distinct integers called candidates and a target integer, target. Your task is to find all unique combinations of numbers from the candidates that add up to the target. Each number from the array can be used multiple times in the combinations. However, combinations are considered unique based on the frequency of numbers used, not the order in which they appear. You will need to be able to return these combinations in any sequence, but each combination should sum to the target value. Given constraints ensure that the solutions will be computationally feasible since the combinations will not exceed 150 for any 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:

[]

Constraints

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

Approach and Intuition

When tackling problems involving combinations that meet certain criteria, it's efficient to use a backtracking approach which can systematically explore all potential candidate solutions. Here's how one might think about solving this problem:

1. Initialization: Start with an empty combination list and a function that tracks the current combination and the remaining sum needed to reach the target.

2. Recursive Backtracking:

   • Check if the remaining sum is zero. If yes, add the current combination to the result, since it means the elements of the current combination sum to the target.
   • Iterate over each number in the candidates list. If a number is greater than the remaining sum, skip to the next iteration because using that number would exceed the target.
   • If a number is less than or equal to the remaining sum, add that number to the current combination and recursively attempt to find the valid combinations with the new sum reduced by the selected number.

3. Backtrack:

   • Once a number is explored (i.e., either leads to a valid combination or proves unsuitable), remove it from the current combination (this step is crucial and handled in the recursion stack upon return).
   • Continue with the next number.

This approach ensures all potential combinations are considered, leveraging the capability of recursion and backtracking to handle the complexity implicit in the variable number of ways the candidates can sum to the target.

Examples Revisited:

• Example 1: The array [2,3,6,7] to meet a target of 7 could achieve the sum with [7] directly or combine smaller numbers like [2,2,3].
• Example 2: With more variety in candidates like [2,3,5] aiming for a target of 8, combinations vary from multiple small numbers [2,2,2,2] to a mix of all available numbers like [2,3,3] and [3,5].
• Example 3: Demonstrates the scenario where no combinations can meet the target (e.g., [2] cannot meet target 1), therefore, results in an empty list.

Solutions

class Solution {
public:
    void searchCombos(int target, vector<int>& current, int startIdx,
                      const vector<int>& numbers,
                      vector<vector<int>>& allCombos) {
        if (target == 0) {
            allCombos.push_back(current);
            return;
        } else if (target < 0) {
            return;
        }
    
        for (int i = startIdx; i < numbers.size(); ++i) {
            current.push_back(numbers[i]);
            searchCombos(target - numbers[i], current,
                         i,  // keep i to allow duplicates
                         numbers, allCombos);
            current.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int goal) {
        vector<vector<int>> allCombos;
        vector<int> tempCombo;
    
        searchCombos(goal, tempCombo, 0, candidates, allCombos);
        return allCombos;
    }
};