Combination Sum II (Leetcode 40)

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

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    
        ans=[]
        
        def recursion(candidates,target,tempSum,tempAns):
            
            if(tempSum==target):
                ans.append(tempAns)
                return
            elif(tempSum>target):
                return
                   
            if(len(candidates)==0):
                return
            
            ele=candidates[0]
            temp=tempAns[:]
            temp.append(ele)
            
            # Considering the element
            recursion(candidates[1:],target,tempSum+ele,temp)
            
            # Ignoring the element
            # When ignoring ignore all other occurances
            i=0
            while(i+1<len(candidates) and candidates[i]==candidates[i+1]):
                i+=1
            
            recursion(candidates[i+1:],target,tempSum,tempAns)
            
            
        candidates.sort()
        recursion(candidates,target,0,[])
        return ans

Last updated