mafeshsho8lmafeshsho8l
Get Started
All coding questions

Combination Sum

medium
NeetCode 150backtrackingarrays

Problem

Given distinct positive candidates and a target, return all unique combinations that sum to the target. Each candidate may be used any number of times, and combinations differing only in order count once.

Examples

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Two combinations reach seven.
Input: candidates = [2], target = 1
Output: []
No combination sums to one.

Constraints

  • • 1 <= candidates.length <= 30
  • • 1 <= candidate value <= 200
  • • 1 <= target <= 500
Hints(tap to reveal)
  • 1. Allow reusing the current index to permit repeats.
  • 2. Stop a branch when the running sum exceeds the target.
Optimal approach(spoiler)
  1. Recurse carrying a start index and the remaining target.
  2. At each step try the current candidate, staying on the same index to allow reuse.
  3. Subtract it from the remaining target and recurse.
  4. Record a combination when the remaining target hits zero, prune when it goes negative.
  5. Backtrack to explore the next candidate.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor