Facebook PixelCombination Sum — Coding Practice
Combination SumMedium

Combination Sum

Medium 18.2k69% acceptance
ArrayBacktracking

Given an array of distinct positive integers candidates and a target integer target, return all unique combinations of candidates that sum to target.

The same candidate may be chosen any number of times. Two combinations are the same if they use the same multiset of numbers (order does not matter).

Output ordering (required, so the answer is deterministic): return each individual combination as a list sorted in ascending order, and return the overall list of combinations sorted lexicographically (compare element by element; a shorter list that is a prefix of a longer one comes first).

Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
2+2+3 = 7 and 7 = 7. Each combination is sorted ascending, and [2,2,3] precedes [7] lexicographically because 2 < 7.
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Three ways to reach 8, listed in lexicographic order.
Example 3
Input: candidates = [2], target = 1
Output: []
No combination of 2s sums to 1.
Constraints
  • 1 ≤ candidates.length ≤ 30
  • 2 ≤ candidates[i] ≤ 40
  • All candidates are distinct.
  • 1 ≤ target ≤ 40
Asked atAmazonGoogleMetaAirbnb
JavaScript
Loading editor…
Case 1
[2,3,6,7], 7
expected: [[2,2,3],[7]]
Case 2
[2,3,5], 8
expected: [[2,2,2,2],[2,3,3],[3,5]]
Case 3
[2], 1
expected: []
Case 4
[1], 2
expected: [[1,1]]
Case 5
[7,3,2], 7
expected: [[2,2,3],[7]]
Case 6
[3,5,8], 11
expected: [[3,3,5],[3,8]]
Case 7
[2,4], 6
expected: [[2,2,2],[2,4]]