Combination Sum

medium

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.

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

candidates = [2,3,6,7], target = 7

Expected Output

[[2,2,3],[7]]

Input

candidates = [2,3,5], target = 8

Expected Output

[[2,2,2,2],[2,3,3],[3,5]]

Input

candidates = [2], target = 1

Expected Output

[]

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Hints

Hint 1 — click to reveal

Combinations, not permutations — [2,3] and [3,2] are the same answer.

Hint 2 — click to reveal

Passing a start index into the recursion prevents you from generating reorderings.

Java Compiler