代码随想录算法训练营第26天 | 回溯02：39. 组合总和、40.组合总和II、131.分割回文串

39. 组合总和
    https://leetcode.cn/problems/combination-sum/
    代码随想录
    https://programmercarl.com/0039.组合总和.html
    40.组合总和II
    https://leetcode.cn/problems/combination-sum-ii/description/
    代码随想录
    https://programmercarl.com/0040.组合总和II.html#算法公开课
    131.分割回文串
    https://leetcode.cn/problems/palindrome-partitioning/description/
    代码随想录
    https://programmercarl.com/0131.分割回文串.html#其他语言版本

39. 组合总和

题解思路

• 组合问题老方法；
• 可重复，所以index不用加一

题解代码：

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def back_track(self,candidates,target,index):
        if sum(self.path)>target:
            return
        if sum(self.path)==target:
            self.res.append(self.path[:])
            return self.res
        for i in range(index,len(candidates)):
            self.path.append(candidates[i])
            self.back_track(candidates,target,i)
            self.path.pop()

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if len(candidates)==0:
            return self.res
        self.back_track(candidates,target,0)
        return self.res

40.组合总和II

题解思路

• 不能重复
  • 重排序
  • 去重
• 剪枝：
  • 减去同一个树层上重复的元素；
  • 同一树支上元素重复可以；

题解代码

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def back_track(self,candidates,target,index):
        if sum(self.path)==target:
            if self.path not in self.res:
                self.res.append(self.path[:])
            return self.res

        if sum(self.path)>target:
            return

        for i in range(index,len(candidates)):
            if i>index and candidates[i]==candidates[i-1]:
                continue
            self.path.append(candidates[i])
            self.back_track(candidates,target,i+1)
            self.path.pop()

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if len(candidates)==0:
            return self.res
        candidates = sorted(candidates)
        self.back_track(candidates,target,0)
        return self.res

131.分割回文串

题解思路

• 按位切割字符串
• 判断字符串是否为回文字符串
• 优化也在判断处

题解代码

class Solution:
    def __init__(self):
        self.curr = []
        self.res = []
    def panduan(self,s):
        if s==s[::-1]:
            return True
    def back_trace(self,s,index):
        if index==len(s):
            self.res.append(self.curr[:])
            return
        for i in range(index+1,len(s)+1):
            if self.panduan(s[index:i]):
                self.curr.append(s[index:i])
                self.back_trace(s,i)
                self.curr.pop()

    def partition(self, s: str) -> List[List[str]]:
        if len(s)==0:
            return self.res
        self.back_trace(s,0)
        return self.res