How do you approach Combination Sum?

Sort the candidates array first to help with pruning.

What is the time complexity of Combination Sum?

Time complexity: O(n^(t/m)) where t is target and m is the minimum candidate. Space complexity: O(t/m) for the recursion depth.

What are common mistakes on Combination Sum?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Combination Sum

MediumAlgorithms

Description

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.

Example 1

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

Output: [[2,2,3],[7]]

Explanation: 2 + 2 + 3 = 7 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

Combination Sum: approach, complexity and pitfalls

A medium backtracking problem, graded against 6 test cases (3 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 3-step hint ladder

Sort the candidates array first to help with pruning.
Use backtracking - at each step, decide whether to include the current candidate again or move to the next.
To avoid duplicate combinations, only consider candidates at the current index or later.

The optimal approach

Show the approach: Backtracking with Pruning

Sort candidates, then use backtracking. At each step, try including the current candidate (can reuse) or skip to the next. Stop early if remaining target becomes negative.

Time: O(n^(t/m)) where t is target and m is the minimum candidate
Space: O(t/m) for the recursion depth

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.