Asked at

Combination Sum

Medium
VerifiedBacktrackingArrayRecursion~25 min

Given an array of distinct positive integers candidates and a target, return all unique combinations where the chosen numbers sum to target.

The same candidate may be reused unlimited times. Two combinations are unique if their multisets differ. Return them in any order.

The input arrives as a single object { candidates, target }.

Examples

in{ candidates: [2, 3, 6, 7], target: 7 }
out[[2,2,3], [7]]

2+2+3 = 7 and 7 = 7; each candidate may be reused.

in{ candidates: [2, 3, 5], target: 8 }
out[[2,2,2,2], [2,3,3], [3,5]]

Three distinct multisets sum to 8.

Constraints

  • 1 ≤ candidates.length ≤ 30
  • 2 ≤ candidates[i] ≤ 40
  • All candidates are distinct positives.
  • 1 ≤ target ≤ 40

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.