Build a Target Sum by Reusing Candidates Freely

Implement combinationSum

You're given an array of distinct positive integers, candidates, and a target. Find every distinct combination of candidates that adds up exactly to target — the same candidate can be picked as many times as needed, but no two combinations in the result should be the same multiset of values. A brute-force search can find every one of these by extending every path it can think of and only checking the sum at the end (or, worse, checking it redundantly at every step without remembering it). The real win comes from carrying the running sum forward instead of recomputing it, and from cutting a branch the instant it's provably hopeless — sorting first turns "hopeless" into a single comparison instead of a search.

Example 1:

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

Output: [[8,8],[3,5,8],[3,3,5,5]]

Example 2:

Input: candidates = [4,6,9], target = 13

Output: [[4,9]]

Example 3:

Input: candidates = [5,7], target = 3

Output: []

+ 9 hidden test cases run on Submit.

Constraints:

  • 1 ≤ candidates.length ≤ 15
  • 2 ≤ candidates[i] ≤ 30, and every value in candidates is distinct
  • 1 ≤ target ≤ 40
  • The same candidate may be reused any number of times within one combination

candidates =

[3, 5, 8]

target =

16