Learn_Algorithm/39_Combination_Sum.py at master · 666syh/Learn_Algorithm · 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
"""
https://leetcode.com/problems/combination-sum/
"""
"""
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target),
find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:
    Input: candidates = [2,3,6,7], target = 7,
    A solution set is:
    [
        [7],
        [2,2,3]
    ]

Example 2:
    Input: candidates = [2,3,5], target = 8,
    A solution set is:
    [
        [2,2,2,2],
        [2,3,3],
        [3,5]
    ]
"""


class Solution:
    def combinationSum(self, candidates, target):
        results = []
        candidates.sort()
        self.search(candidates, target, results, [])
        return results


    def search(self, candidates, target, results, result):
        for i in range(len(candidates)):
            temp = target
            if candidates[i]<=temp:
                temp -= candidates[i]
                if temp == 0:
                    l = result+[candidates[i]]
                    l.sort()
                    if l not in results:
                        results.append(l)
                    break
                else:
                    self.search(candidates, temp, results, result+[candidates[i]])
            else:
                break


x = Solution()
print(x.combinationSum([8,7,4,3], 11))