CombinationsSum.py

# Question link - https://leetcode.com/problems/combination-sum/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # This uses Brute Forced approch
        res = [] 

        # Recursive function 
        def dfs(i, cur , total):
            # Basecase 
            if total == target:
                res.append(cur.copy())
                return 

            if i >= len(candidates) or total > target:
                return 

            # We have two path - 1st include 2
            cur.append((candidates[i]))
            dfs(i, cur , total + candidates[i])
            #2nd is not include 2
            cur.pop()
            dfs(i+1, cur , total)

        # Call 
        dfs(0 , [] , 0)
        return res