DSA · Backtracking · #51
Combination Sum
Module 52 · difficulty 3/5·⏱ 30:00starts on first keystroke
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. Implement `combinationSum(candidates, target)` returning an array of integer arrays.
Examples
candidates = [2,3,6,7], target = 7→[[2,2,3],[7]]— 2+2+3 = 7 and 7 = 7. These are the only two combinations.candidates = [2,3,5], target = 8→[[2,2,2,2],[2,3,3],[3,5]]candidates = [2], target = 1→[]— No combination sums to 1.
Constraints
- · 1 <= candidates.length <= 30
- · 2 <= candidates[i] <= 40
- · All elements of candidates are distinct.
- · 1 <= target <= 40
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.