回溯算法39|40|131

39组合总和

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.backTracking(candidates, target, 0, 0)
        return self.result

    def backTracking(self, candidates, target, cur_sum, start_index) -> List:
        if cur_sum > target:
            return
        if cur_sum == target:
            self.result.append(self.path[:])
        for i in range(start_index, len(candidates)):
            if cur_sum + candidates[i] <= target:
                cur_sum += candidates[i]
                self.path.append(candidates[i])
                self.backTracking(candidates, target, cur_sum, i)
                cur_sum -= candidates[i]
                self.path.pop()

40组合总和II

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        used = [0] * len(candidates)
        cur_sum = 0
        start_index = 0
        self.backTracking(candidates, target, used, cur_sum, start_index)
        return self.result

    def backTracking(self, candidates, target, used, cur_sum, start_index) -> List:
        if cur_sum == target:
            self.result.append(self.path[:])
        for i in range(start_index, len(candidates)):
            if i > start_index and candidates[i] == candidates[i - 1] and used[i - 1] == 0:
                continue
            if cur_sum + candidates[i] <= target:
                cur_sum += candidates[i]
                used[i] = 1
                self.path.append(candidates[i])
                self.backTracking(candidates, target, used, cur_sum, i + 1)
                cur_sum -= candidates[i]
                used[i] = 0
                self.path.pop()

131分割回文串

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def isPalindrome(self, sub_s):
        left = 0
        right = len(sub_s) - 1
        while left <= right:
            if sub_s[left] != sub_s[right]:
                return False
            left += 1
            right -= 1
        return True

    def partition(self, s: str) -> List[List[str]]:
        self.backTracking(s, 0)
        return self.result

    def backTracking(self, s, start_index) -> List:
        if start_index >= len(s):
            self.result.append(self.path[:])
            return
        for i in range(start_index + 1, len(s) + 1):
            sub_s = s[start_index:i]
            if self.isPalindrome(sub_s):
                self.path.append(sub_s)
            else:
                continue
            self.backTracking(s, i)
            self.path.pop()