1
class Solution:
2
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
3
        self.path = []       # 当前组合路径
4
        self.res = []        # 所有合法组合
5
        self.sum = 0         # 当前组合的总和
6
        candidates.sort()    # 排序用于剪枝
7
        self.backtrack(candidates, target, 0)
8
        return self.res
9

10
    def backtrack(self, candidates, target, start):
11
        if self.sum == target:
12
            self.res.append(self.path[:])
13
            return
14
        for i in range(start, len(candidates)):
15
            if self.sum + candidates[i] > target:  # 剪枝
16
                break
17
            self.sum += candidates[i]
18
            self.path.append(candidates[i])
19
            self.backtrack(candidates, target, i)  # 可重复使用元素：i 而不是 i+1
20
            self.sum -= candidates[i]
21
            self.path.pop()

1
class Solution:
2
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
3
        self.path = []
4
        self.res = []
5
        self.sum = 0
6
        candidates.sort()  # 排序后方便跳过重复元素
7
        self.backtrack(candidates, target, 0)
8
        return self.res
9

10
    def backtrack(self, candidates, target, start):
11
        if self.sum == target:
12
            self.res.append(self.path[:])
13
            return
14
        for i in range(start, len(candidates)):
15
            if candidates[i] + self.sum > target:
16
                break  # 剪枝
17
            # 这里判断 i > start 而不是 i > 0 是因为我们需要跳过同一层的重复元素
18
            if i > start and candidates[i] == candidates[i - 1]:
19
                continue  # 跳过同层重复
20
            self.sum += candidates[i]
21
            self.path.append(candidates[i])
22
            self.backtrack(candidates, target, i + 1)  # 元素不可重复使用：i+1
23
            self.sum -= candidates[i]
24
            self.path.pop()

1
class Solution:
2
    def partition(self, s: str) -> List[List[str]]:
3
        self.path = []  # 当前回文分割路径
4
        self.res = []   # 所有合法回文组合
5
        self.backtrack(s, 0)
6
        return self.res
7

8
    def backtrack(self, s, start):
9
        if start == len(s):
10
            self.res.append(self.path[:])
11
            return
12
        for i in range(start, len(s)):
13
            if not self.isPalindrome(s, start, i):
14
                continue
15
            self.path.append(s[start:i + 1])   # 做选择
16
            self.backtrack(s, i + 1)           # 递归处理剩余子串
17
            self.path.pop()                    # 撤销选择
18

19
    def isPalindrome(self, s, l, r):
20
        while l < r:
21
            if s[l] != s[r]:
22
                return False
23
            l += 1
24
            r -= 1
25
        return True