combination_sum
1# @leet start 2from sortedcontainers import SortedList 3 4 5class Solution: 6 def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]: 7 """ 8 This question requires us to just backtrack and find all of the combination 9 sums. To do so, we have a visited set (so we don't do any extra work), and 10 a res set, which stores all of our results. 11 12 We backtrack through, where for every round, we add a candidate to our 13 current sum, and at the top, we check to make sure the sum is the right 14 amount. 15 16 We use a sorted list to make hashing a little easier (otherwise it requires 17 sorting the list before putting it in the visited set), and return 18 the result. 19 """ 20 visited = set() 21 res = set() 22 23 def traverse(curr_sum, path): 24 if tuple(path) in visited: 25 return 26 if curr_sum > target: 27 return 28 if curr_sum == target: 29 res.add(list(path)) 30 return 31 32 visited.add(tuple(path)) 33 34 for candidate in candidates: 35 path.add(candidate) 36 traverse(curr_sum + candidate, path) 37 path.remove(candidate) 38 39 traverse(0, SortedList()) 40 return list(list(res)) 41 42 43# @leet end 44 45 46def test(): 47 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]: 8 """ 9 This question requires us to just backtrack and find all of the combination 10 sums. To do so, we have a visited set (so we don't do any extra work), and 11 a res set, which stores all of our results. 12 13 We backtrack through, where for every round, we add a candidate to our 14 current sum, and at the top, we check to make sure the sum is the right 15 amount. 16 17 We use a sorted list to make hashing a little easier (otherwise it requires 18 sorting the list before putting it in the visited set), and return 19 the result. 20 """ 21 visited = set() 22 res = set() 23 24 def traverse(curr_sum, path): 25 if tuple(path) in visited: 26 return 27 if curr_sum > target: 28 return 29 if curr_sum == target: 30 res.add(list(path)) 31 return 32 33 visited.add(tuple(path)) 34 35 for candidate in candidates: 36 path.add(candidate) 37 traverse(curr_sum + candidate, path) 38 path.remove(candidate) 39 40 traverse(0, SortedList()) 41 return list(list(res))
def
combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
7 def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]: 8 """ 9 This question requires us to just backtrack and find all of the combination 10 sums. To do so, we have a visited set (so we don't do any extra work), and 11 a res set, which stores all of our results. 12 13 We backtrack through, where for every round, we add a candidate to our 14 current sum, and at the top, we check to make sure the sum is the right 15 amount. 16 17 We use a sorted list to make hashing a little easier (otherwise it requires 18 sorting the list before putting it in the visited set), and return 19 the result. 20 """ 21 visited = set() 22 res = set() 23 24 def traverse(curr_sum, path): 25 if tuple(path) in visited: 26 return 27 if curr_sum > target: 28 return 29 if curr_sum == target: 30 res.add(list(path)) 31 return 32 33 visited.add(tuple(path)) 34 35 for candidate in candidates: 36 path.add(candidate) 37 traverse(curr_sum + candidate, path) 38 path.remove(candidate) 39 40 traverse(0, SortedList()) 41 return list(list(res))
This question requires us to just backtrack and find all of the combination sums. To do so, we have a visited set (so we don't do any extra work), and a res set, which stores all of our results.
We backtrack through, where for every round, we add a candidate to our current sum, and at the top, we check to make sure the sum is the right amount.
We use a sorted list to make hashing a little easier (otherwise it requires sorting the list before putting it in the visited set), and return the result.
def
test():