Coding

Combination Sum

Asked at

eBay

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Provided with a goal integer target and an array of unique integer candidates, provide a list of all possible combinations of candidates in which the selected numbers add up to the target. The combinations can be returned in any order.

A candidate may be selected from the pool an infinite number of times. There are two distinct combinations if the frequency of at least one of the selected figures differs.

The test cases are created so that, for the given input, there are fewer than 150 possible combinations that add up to the target. If there is no possible subsequences then return empty vector.

Input : candidates = [2, 3, 5, 4] , target = 7 Output : [ [2, 2, 3] , [3, 4] , [5, 2] ] Explanation : 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 5 and 2 are candidates, and 5 + 2 = 7. 3 and 4 are candidates, and 3 + 4 = 7. There are total three combinations.

Input : candidates = [2], target = 1 Output : [] Explanation : There is no way we can choose the candidates to sum up to target.

Input : candidates = [3, 4, 5, 6], target = 10

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

cpp

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //your code goes here
    }
};

java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //your code goes here
    }
}

python

class Solution:
    def combinationSum(self, candidates, target):
        #your code goes here

javascript

class Solution {
    combinationSum(candidates, target) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public List<List<int>> CombinationSum(int[] candidates, int target)
    {
        // your code goes here
    }
}

func combinationSum(candidates []int, target int) [][]int {

}

Stuck? Show a way to structure it+

01Sort candidates for deterministic pruning.
02Recurse with a start index and remaining target.
03Emit the path at remaining zero.
04Choose the same index again to permit reuse.
05Advance indices to avoid reordered duplicates.

Reference answer

Sort the unique candidates and recurse with start, remaining, and path. For every index i from start onward, stop once candidates[i] exceeds remaining. Choose the value, recurse with the same i because a candidate may be used indefinitely, then remove it from the path. When remaining is zero, append a copy. Passing i rather than zero prevents [2, 5] and [5, 2] from appearing as separate combinations. Sorting is not strictly required if values are unique, but it makes pruning and stable output straightforward. The search is output-sensitive and exponential in the worst case; describe it as O(number of explored states plus output size), not polynomial. Recursion depth is at most target divided by the minimum candidate, so auxiliary path space is that depth excluding returned combinations.

Then expect these follow-ups

How does this change when each number may be used once?
Tests: constraint adaptation
How would you count combinations instead of listing them?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question