Related: Coin Change
Intuition
- On each recursion, you have a choice whether to keep the current element, or to not keep the element and go on to the next index.
- Every time you recurse, you are moving closer and closer to target. Therefore, you are guaranteed to hit or exceed target after a certain point.
- If you hit the target or exceed it, backtrack to the parent node.
- This is essentially a DFS preorder traversal of the nodes. If you sort, and the left child exceeds target, then you do not need to compute the right subtree since if you are sorted, if the left subtree which contains a smaller element exceeds target, that same subtree with instead a larger element would also exceed target. So, just return in that case.
Runtime
- Through time, you bound by the smallest element which gets added.
Code
Much Cleaner Using just DFS
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
res = []
def r(index, sub, cur_sum):
if index >= n:
return False
if cur_sum >= target:
if cur_sum == target:
res.append(sub.copy())
return True
sub.append(candidates[index])
is_overflow = r(index, sub, cur_sum + candidates[index])
sub.pop()
if not is_overflow:
r(index + 1, sub, cur_sum)
return False
r(0, [], 0)
return resFastest Solution
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
cur = []
candidates.sort()
n = len(candidates)
def r(index, cur_sum):
if index >= n:
return False
if cur_sum >= target:
if cur_sum == target:
res.append(cur.copy())
return True
for i in range(index, n):
cur.append(candidates[i])
is_overflow = r(i, cur_sum + candidates[i])
cur.pop()
if is_overflow:
break
return False
r(0, 0)
return res