141. Combination Sum

PRO

Medium

Topics

Companies

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

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

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

Explanation: The combination [2, 2, 3] sums to 7 (2+2+3=7), and [7] also sums to 7. These are the only unique combinations.

Example 2:

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

Output: [[2,2,2,2],[2,3,3],[3,5]]

Explanation: The combinations [2,2,2,2], [2,3,3], and [3,5] all sum to 8. These are all possible unique combinations using the given candidates.

Example 3:

Input: candidates = [2], target = 1

Output: []

Explanation: There are no combinations of the number 2 that sum to 1. Therefore, the output is an empty list.

Constraints:

•
•
•
•
•

Use backtracking to explore all combinations. Key insight: since we can reuse elements, pass current index 'i' (not i+1) in recursion. Sort candidates first for optimization (optional). Prune branches when total exceeds target.

Time Complexity

O(n^(target/minCandidate + 1)) (worst-case backtracking)

Space Complexity

O(target/minCandidate) + output size