Find every combination that sums to a target, using each number once. Sort, skip repeats at the same depth, and stop once numbers get too big.
▼The problem
LeetCode 40 (Medium). Given an array candidates (which may contain duplicates) and a target, return all unique combinations of candidates that sum to the target. Each number may be used at most once in a combination, and the answer must not contain duplicate combinations.
Examples (LeetCode's): [10,1,2,7,6,1,5], target 8 → [[1,1,6],[1,2,5],[1,7],[2,6]] (sorted: [1,1,2,5,6,7,10]), and [2,5,2,1,2], target 5 → [[1,2,2],[5]].
The solution
def combinationSum2(nums, target):
nums.sort()
out = []
def go(start, remain, picks):
if remain == 0:
out.append(picks[:])
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
if nums[i] > remain:
break
picks.append(nums[i])
go(i + 1, remain - nums[i], picks)
picks.pop()
go(0, target, [])
return outTranscript
Combination Sum Two. Given numbers that may repeat, and a target, return every unique combination summing to the target. Unlike Combination Sum, each number is used once, and duplicates can't repeat answers.
Take ten, one, two, seven, six, one, five, target eight. A toll booth wants exact change: one, one, six; one, two, five; one, seven; or two, six. Or two, five, two, one, two, target five: one, two, two, or five.
The naive way tries two to the n subsets, keeps sums of eight, dedupes with a set. With two ones, one, seven and one, two, five each turn up twice: wasted work.
Sort, then backtrack from a start index. At each depth, skip a number equal to the one before it: already tried there. Once a number is bigger than what's left, stop; the rest are bigger too. Recurse from the next index, so each is used once.
In code: when nothing remains, save the picks. Loop from start: skip twins, break when too big, pick, recurse with i plus one, and pop.
Pay eight. One, one, two leaves four; five's too big. One, one, five leaves one. One, one, six: save. One, two, five: save. One, five and one, six fall short. One, seven: save. At the top, skip the second one. Two, six: save. Five, six, seven: too little left; ten's over eight.
Worst case, every subset is explored and each answer copied: order two to the n times n time. The recursion takes order n space.
Sort, skip twins, stop early. That's Combination Sum Two.