Combination Sum

The key idea

Build combinations with depth-first backtracking. Because each number may be reused, recurse with the SAME start index i (not i + 1); to avoid duplicate combinations like [2,3] and [3,2], never look at a candidate before the current start. Prune a branch as soon as the running sum exceeds target.

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 from candidates may be chosen an unlimited number of times. Two combinations are different if the frequency of at least one chosen number is different.

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

Constraints

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

Examples

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]]

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

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

Complexity

Time: O(N^(T/M)) Space: O(T/M)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →