39. 组合总和

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        path = []
        result = []
        def backtracking(candidates, target, sum_nums, start_index):
            if sum_nums > target:
                return
            if sum_nums == target:
                result.append(path[:])
                return
            for i in range(start_index, len(candidates)):
                path.append(candidates[i])
                sum_nums += candidates[i]
                backtracking(candidates, target, sum_nums, i)
                path.pop()
                sum_nums -= candidates[i]
        #这里是对数组操作，所以start_index从0开始
        backtracking(candidates, target, 0, 0)
        return result

40.组合总和II

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        path = []
        result = []
        used = [0] * len(candidates)
        candidates.sort()
        def backtracking(candidates, target, sum_nums, start_index, used):
            if sum_nums > target:
                return
            if sum_nums == target:
                result.append(path[:])
                return
            for i in range(start_index, len(candidates)):
                # 判断used[i - 1] == 0，进行树层去重，保留树枝的重复值
                if i > 0 and candidates[i] == candidates[i-1] and used[i - 1] == 0: 
                    continue
                path.append(candidates[i])
                sum_nums += candidates[i]
                used[i] = 1
                backtracking(candidates, target, sum_nums, i + 1, used)
                path.pop()
                sum_nums -= candidates[i]
                used[i] = 0
        backtracking(candidates, target, 0, 0, used)
        return result

131.分割回文串

class Solution:
    def partition(self, s: str) -> List[List[str]]:

        path = []
        result = []
        def backtracking(s, start_index):
            if start_index == len(s):
                result.append(path[:])
                return
            for i in range(start_index, len(s)):
                temp = s[start_index : i + 1]
                if temp == temp[::-1]:
                    path.append(temp)
                    backtracking(s, i + 1)
                    path.pop()
                else:
                    continue
        backtracking(s, 0)
        return result