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