Leetcode-Solutions/LC40.py at master · pratul2789/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        vis = set()
        ans = []
        candidates.sort()
        res = set()

        def helper(index,path,vis,total,target):
            if tuple(path) in res:
                return

            if total > target:
                return

            if total == target:
                ans.append([i for i in path])
                return

            for i in range(index,len(candidates)):
                if i > index and candidates[i] == candidates[i-1]:
                    continue
                path.append(candidates[i])
                helper(i+1,path,vis,total+candidates[i],target)
                path.pop()

        helper(0,[],vis,0,target)
        return ans