Developers

Combination Sum

MediumBacktrackingAlso known as LeetCode 39

You are given a list candidates of distinct positive integers and a target. Return every distinct combination of candidates that adds up to target. A number may be used as many times as you like.

Two combinations are the same if they use each number the same number of times, whatever the order. You may return the combinations in any order, and the numbers inside one combination in any order. It is guaranteed that the number of combinations is less than 150 for every input.

Examples

Input candidates = [2, 3, 6, 7], target = 7
Output [[2, 2, 3], [7]]
Input candidates = [2, 3, 5], target = 8
Output [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Input candidates = [2], target = 1
Output []
No combination reaches the target.

Constraints

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40, and all the candidates are different
  • 1 <= target <= 40

Stuck? Take one hint at a time

Common mistakes
  • Starting the loop at 0 in each call, which gives [2, 3] and [3, 2] as different answers.
  • Passing i + 1 instead of i to the recursive call, which forbids reusing a number.
  • Appending current itself to the results instead of a copy.
  • Not stopping when the remainder goes negative, so the recursion never ends.
  • In the table version, looping over totals before candidates, which lists the same combination in several orders.
Questions an interviewer may ask next
  • Each candidate may be used at most once, and the list may contain duplicates. (Combination Sum II: sort, move forward by one, skip equal neighbors.)
  • Return only how many combinations there are. (Coin Change II: the same table with counts instead of lists.)
  • Count the ordered sequences, so [2, 3] and [3, 2] differ. (Combination Sum IV: loop over totals first, then candidates.)
  • What makes the running time hard to state tightly, and what bound can you give using the smallest candidate?