Start learning free

LESSON 416 OF 678 · BACKTRACKING

Combination Sum

Practice O(nt/m)

You get an array candidates of distinct integers and an integer target. Return every combination of candidates that adds up to target.

You may use a candidate as many times as you like.

The order inside a combination doesn't matter. 4 + 3 + 3 is the same combination as 3 + 3 + 4. List it only once.

Write each combination in ascending order. List the combinations in lexicographic order. The first position where two combinations differ decides which comes first.

If no combination adds up to target, return an empty array.

 

Example 1:

Input: candidates = [4,3,5], target = 10
Output: [[3,3,4],[5,5]]
Explanation: 3 + 3 + 4 = 10 uses the 3 twice.
5 + 5 = 10 uses the 5 twice.
The candidates come unsorted, but each combination is in ascending order.

Example 2:

Input: candidates = [3,9,6], target = 9
Output: [[3,3,3],[3,6],[9]]
Explanation: The first two combinations both start with 3.
Their second numbers are 3 and 6.
So [3,3,3] comes first.
[9] starts with 9, so it is last.

Example 3:

Input: candidates = [4,6], target = 9
Output: []
Explanation: Any sum of 4s and 6s is even, so it can never be 9.

 

Constraints:

  • candidates holds 1 to 30 numbers.
  • No number appears twice.
  • Each candidate is between 2 and 40.
  • target is between 1 and 40.

Note:

The tutorial uses backtracking. Sort candidates, then build a combination one number at a time: try every candidate from the position of the last number chosen onward (that same number included, since numbers can repeat), go deeper with what is left of target, then remove the number again and try the next one. Starting from the last chosen position builds each combination exactly once, already in ascending order, and the combinations come out in lexicographic order. Because the candidates are sorted, the loop can stop at the first one that is bigger than what is left.

The search is exponential: with n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each of them is one of n candidates, so the time is O(nt/m) in the worst case. Besides the answer, the extra space is O(t / m): the combination being built and one call per number in it.

STEP 1 OF 13
    Ctrl + Enter to check