Backtracking: given array make combinations of sums python

PHOTO EMBED

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/