class Solution:
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.reslist = []
candidates = sorted(candidates)
self.dfs(candidates,[],target,0)
return self.reslist
def dfs(self,candidates,sublist,target,last):
if target == 0:
self.reslist.append(sublist[:])
if target < candidates[0]:
return
for n in candidates:
if n > target:
return
if n < last:
continue
sublist.append(n)
self.dfs(candidates,sublist,target-n,n)
sublist.pop()
