Combination Sum (Leetcode 39)

Problem Link: https://leetcode.com/problems/combination-sum/

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        ans=[]
        def recursion(candidates,target,tempArr,tempSum):
            
            if(tempSum==target):
                ans.append(tempArr)
                return
            
            elif(tempSum>target):
                return
            
            if(len(candidates)==0):
                if(tempSum==target):
                    ans.append(tempArr)
                return
            
            
            ele=candidates[0]
            temp=tempArr[:]
            temp.append(ele)
            
            # Taking the element
            recursion(candidates,target,temp,tempSum+ele)
            
            # Ignoring the element
            recursion(candidates[1:],target,tempArr,tempSum)
            
        recursion(candidates,target,[],0)
        return ans

Last updated