Given a list of candidates and a target, target, we’re asked to return all combinations of the input that sum to that target, without duplicates.
Sorting the input helps us avoid creating duplicate combinations as we can avoid traversing paths with the same starting number. We maintain a running total used to determine if we should select a path after checking the sum of the current number against the running total - if it’s less than the target we traverse the path.
Once the sum of the combination is equal to the target, we append it to our answer list and terminate.
The solution is as follows:
from collections import Counter
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans, n = [], len(candidates)
candidates.sort()
def backtrack(s: List[int], i: int, t: int) -> None:
if t == target:
ans.append(s[:])
return
for j in range(i, n):
if j > i and candidates[j] == candidates[j - 1]:
continue
if candidates[j] + t <= target:
s.append(candidates[j])
backtrack(s, j + 1, t + candidates[j])
s.pop()
else:
return
backtrack([], 0, 0)
return ans_ Time Complexity:
O(2^n) - We create all possible combinations from the input array in the worst case.
_ Space Complexity:
O(n) - Where n is the size of the input, this is our recursion stack.