Combination sum, numbers can repeat
Recurse from the same index instead of the next one, so a number can be chosen more than once. About 10 minutes.
Reuse a number by not moving past it
Last time, picking a number shut the door on it for the rest of that branch, because the next call started just after it. Here each number may be used as often as it fits, like coins in a till where you have plenty of each.
So after picking a number, the next call may pick it again. The change is one index: recurse from the same position instead of the next one. Earlier numbers stay off-limits, which keeps 2 then 3 and 3 then 2 from both appearing.
res = []
def go(start, left, curr):
if left == 0:
res.append(list(curr))
return
for i in range(start, len(nums)):
x = nums[i]
if x > left:
break
curr.append(x)
go(i, left - x, curr)
curr.pop()
go(0, target, [])
return resPick 2: 5 left. The next call starts at 2 again, not after it.
The same break still applies
The numbers are sorted and positive here too, so the pruning is unchanged: the moment a number is bigger than what is left, stop the loop, since everything after it is bigger as well.
The worry with unlimited reuse is recursion that never ends. It can't happen: every number is at least 1, so the amount left shrinks on every pick, and the recursion always reaches zero or runs out of numbers to try.
combination_sum_once uses backtrack(i + 1, ...); combination_sum_unlimited uses backtrack(i, ...). What does that one change let happen?
- AThe number at index i can be chosen again on the very next pick, since it isn't skipped past
- BNumbers can now be picked in any order, not just increasing order
- CIt lets the search skip over some numbers to save time
Show the answer
The number at index i can be chosen again on the very next pick, since it isn't skipped past. Passing i instead of i + 1 keeps nums[i] in the range the next loop scans, so the same value can appear more than once in a combination.
Combination sum, numbers can repeat
Given an array nums of distinct positive integers sorted in increasing order, and an integer target, return every combination of numbers from nums — where each number may be used any number of times, or not at all — whose values sum to exactly target. List the numbers within each combination in non-decreasing order, and list the combinations themselves in lexicographic order.
nums = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]]
1 ≤ nums.length ≤ 8 · 1 ≤ nums[i] ≤ 20 · nums is sorted in strictly increasing order · 1 ≤ target ≤ 30