Backtracking: given array make combinations of sums python
Tue Aug 09 2022 19:43:50 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#depth
#first
#search
#recursive
#neetcode
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
#i is index of candidates
def dfs(i, current, total):
if total == target:
#if you do not add .copu() it will append empty arrays
result.append(current.copy())
return
if i >= len(candidates) or total > target:
return
#decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index
#1) try adding candidates[i]
current.append(candidates[i])
dfs(i, current, total + candidates[i])
#2) move on to next index
current.pop()
dfs(i + 1, current, total)
dfs(0, [], 0)
return result
content_copyCOPY
https://ibb.co/KLwq973: incorrect decision tree. this is more for permutations
https://ibb.co/Xp6QPt8: correct decision tree. you are either adding candidates[i] or not
https://leetcode.com/problems/combination-sum/submissions/
Comments