代码随想录训练营第III期--027--python_代码随想录 python

# 代码随想录训练营第III期--027--python

# 39
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        def backtracking(path, start_index, t):

            if t == 0:
                if path not in res:
                    res.append(path)
                return 
            if t < 0:
                return 
            for i in range(start_index, len(candidates)):
                backtracking(path + [candidates[i]], i, t - candidates[i])
                # backtracking(path, i + 1, t)
        backtracking([], 0, target)
        return res 


# 40 按照上一个答案，超时了

    # def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    #     if sum(candidates) == target: return [candidates]
    #     if sum(candidates) < target: return []
    #     res = []
    #     candidates.sort()
    #     def backtrack(path, start_i, t):
    #         if t == 0:
    #             path.sort()
    #             if path not in res:
    #                 res.append(path)
    #             return 
    #         if t < 0:
    #             return 
    #         for i in range(start_i, len(candidates)):
    #             backtrack(path + [candidates[i]], i + 1, t - candidates[i])
    #             backtrack(path, i+1, t)
    #     backtrack([], 0, target)
    #     return res 

    # 去重就ac了
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if sum(candidates) == target: return [candidates]
        if sum(candidates) < target: return []
        res = []
        candidates.sort()
        def backtrack(path, start_i, t):
            if t == 0:
                path.sort()
                if path not in res:
                    res.append(path)
                return 
            if t < 0:
                return 
            for i in range(start_i, len(candidates)):
                if i > start_i and candidates[i] == candidates[i - 1]: # 这里去重的
                    continue
                backtrack(path + [candidates[i]], i + 1, t - candidates[i])
                # backtrack(path, i+1, t)
        backtrack([], 0, target)
        return res 


# 131 
# 套用上面的模板不好使
    # def partition(self, s: str) -> List[List[str]]:
    #     res = []
    #     def backtrack(path, index, temp):
    #         if index == len(s) - 1:
    #             if path not in res:
    #                 res.append(path)
    #             return 
    #         for i in range(index, len(s)):
    #             if temp == temp[::-1] and temp != '' and temp not in path:
    #                 path.append(temp)
    #             backtrack(path, index + 1, temp + s[i])
    #             # backtrack(path, index + 1, temp)
    #     backtrack([], 0, '')
    #     return res 

    def partition(self, s: str) -> List[List[str]]:
        res = []
        def backtrack(path, index):
            if index == len(s):
                if path not in res:
                    res.append(path)
                return 
            for i in range(index, len(s)):
                temp = s[index:i+1]
                if temp == temp[::-1] and temp != '' :
                    backtrack(path + [temp], i + 1)
                # backtrack(path, index + 1, temp)
        backtrack([], 0)
        return res 
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96