Related: Combination Sum
Intuition
- The key for this problem is that you start recursing at each index. For that reason specifically, you need a for loop within your recursive function to simulate each starting point.
- Then, at each starting point, you choose whether to keep or not to keep the index in question.
- However, you need more granular control for this question, since you wish to skip using the same element index as a starting point, since you would get duplicate subarrays, which a seen set would clear up, but you would be doing unnecessary computation since:
- If your array is sorted and you already started at the same element, you would get the same results (since you computed starting from the previous element which included the current element’s computations).
Runtime
due to a complete search in which you select or do not select on each iteration.
Code
Solution
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 resTLE
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
cur = []
res = []
def r(index, cur_sum):
if index >= n:
return
if cur_sum >= target:
if cur_sum == target and cur not in res:
res.append(cur.copy())
return
for i in range(index + 1, n):
cur.append(candidates[i])
r(i, cur_sum + candidates[i])
cur.pop()
for i in range(n):
cur.append(candidates[i])
r(i, candidates[i])
cur.pop()
return res