aboutsummaryrefslogtreecommitdiff
path: root/combination_sum2.py
blob: d1bbc5e30312cb13700fcb5e7b0251838194ddf9 (plain)
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
34
35
36
37
# 40. Combination Sum II

"""
given a collection of candidate numbers and a target number, find all unique
combinations in 'candidates' where the candidate numbers sum to 'target'.
each number in 'candidates' may only be used once
"""


class Solution(object):
    def dfs(self, candidates, target, idx, path, res):
        if target <= 0:
            if target == 0:
                res.append(path)
            return
        for i in range(idx, len(candidates)):
            if i > idx and candidates[i] == candidates[i - 1]:
                continue
            self.dfs(
                candidates, target - candidates[i], i + 1, path + [candidates[i]], res
            )

    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        ans = []
        self.dfs(sorted(candidates), target, 0, [], ans)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8))
    print(obj.combinationSum2(candidates=[2, 5, 2, 1, 2], target=5))