You get an array candidates and an integer target. A number in candidates may repeat. Return every distinct combination of candidates that adds up to target.
Each candidate can be used at most once. So a number that appears twice in candidates can appear at most twice in a combination.
Copies of a number count as the same. Take [2,2,5] with target = 7. Either 2 with the 5 gives [2,5], so 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. The search in the Note below finds them in this order.
If no combination adds up to target, return an empty array.
Example 1:
Input: candidates = [3,1,4,1,2], target = 5 Output: [[1,1,3],[1,4],[2,3]] Explanation: The candidates hold two 1s, a 2, a 3 and a 4. [1,1,3] uses both 1s. [1,4] works with either 1, but it is listed once. At the second number, 1 is smaller than 4. So [1,1,3] is listed first.
Example 2:
Input: candidates = [4,4,4], target = 8 Output: [[4,4]] Explanation: Any two of the three 4s make 8. They all give the same combination.
Example 3:
Input: candidates = [5,2], target = 4 Output: [] Explanation: 5 alone is too big. The 2 can't be used twice. So nothing adds up to 4.
Constraints:
candidatesholds 1 to 100 numbers.- Each candidate is between 1 and 50.
targetis between 1 and 30.
Note:
The tutorial uses backtracking, as in Combination Sum. Sort candidates. A call gets start, the first index it may still use, remaining, what the combination still needs, and current, the combination built so far. When remaining is 0, it saves a copy of current. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], calls itself with i + 1 and remaining - candidates[i], and removes the number again. Because the candidates are sorted, the loop can stop at the first one that is bigger than remaining.
Two things change from Combination Sum. First, the deeper call starts at i + 1, not at i: there, a number could be chosen again and again; here, each candidate is used at most once. Second, as in Subsets II, the loop skips candidates[i] when i > start and it equals candidates[i - 1]. Inside one call, every turn of the loop picks a different next number, and a second copy of the same value would build exactly the same combinations again. A copy is still taken when it is the first one this call tries, at i = start: that is how [1,1,3] gets its second 1.
The search is exponential: with n candidates, there are at most 2n ways to pick some of them, and copying a combination takes up to n steps, so the time is O(n · 2n) in the worst case. The sorted order keeps it far smaller in practice: the calls only build distinct combinations whose sum is at most target. Besides the answer, the extra space is O(n): the combination being built and one call per number in it.
Free plan: 30 tutor messages. PRO is unlimited.
