Combination Sum

2 min read
LC-Medium
Backtracking

Oct 21, 2022

3 years ago

LeetCode

Solution

Recursive DFS- at any point you have two choices:
- Include the current number, and recur without incrementing the index
  - We include the current number by adding it to cur_sum
- Don't include the current number, and recur with incrementing the index
  - We skip the current number by incrementing i and keeping cur and cur_sum the same.
This way, we make sure that our subtree's wont result in duplicate answers. At any point in the tree, if a number has been used, it won't be used again the right subtree.

Time	Space	Explanation
`O()`	`O()`

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] def dfs(i, cur, cur_sum): if cur_sum > target or i == len(candidates): return if cur_sum == target: ans.append(cur[:]) return cur.append(candidates[i]) dfs(i, cur, cur_sum + candidates[i]) cur.pop() dfs(i + 1, cur, cur_sum) dfs(0, [], 0) return ans

Cleaner Solution

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] def dfs(i, cur, cur_sum): if i == len(candidates) or cur_sum > target: return if cur_sum == target: ans.append(cur) return dfs(i, cur + [candidates[i]], cur_sum + candidates[i]) dfs(i + 1, cur, cur_sum) dfs(0, [], 0) return ans