Combination Sum
On this page
Problem statement
Given an array of distinct positive integers
candidatesand a positivetarget, return every unique combination of candidates whose sum is exactlytarget. Each number may be used any number of times. Two combinations are the same if they use the same numbers the same number of times, in any order, so[3, 5]and[5, 3]count once. The result may be in any order.
The standard "backtracking with reuse" problem. It checks that you can enumerate combinations without producing the same one in different orders, and that you prune the search instead of exploring hopeless branches. Original problem: LeetCode 39.
Example

Input: candidates = [3, 4, 5], target = 8
Output: [[3, 5], [4, 4]]
Input: candidates = [2, 7], target = 11
Output: [[2, 2, 7]]
Input: candidates = [6], target = 4
Output: []
Constraints (assumed)
- 1 ≤ candidates.length ≤ 30; 2 ≤ candidates[i] ≤ 40, all distinct.
- 1 ≤ target ≤ 40; the number of answers is small (under a few hundred).
What this question tests
- Writing a backtracking function with a clear choose / explore / un-choose structure.
- Avoiding duplicate combinations with a start index instead of a set of results.
- Pruning with sorted input, and knowing the output-sensitive complexity.
Questions to ask first
- Can a number be reused? (Here: yes, unlimited times. Combination Sum II allows each once.)
- Are the candidates distinct and positive? Zero or negative numbers would make the search infinite. (Here: distinct and positive.)
- Does the order of numbers inside a combination matter? (Here: no;
[3, 5]=[5, 3].) - Do you need the combinations or just how many there are? Counting is a DP problem and much faster.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.