【leetcode刷刷】39. 组合总和、40.组合总和II、131.分割回文串

39. 组合总和

1. 一开始写的时候没注意到可以重复，注意到可以重复之后就去掉了start_index，但是出现了类似[2,2,3][2,3,2]这种重复。看了题解之后，发现加上start_index，但是进for循环的时候start_index还是i，这样就是既可以重复也不会重新取之前的数。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        self.backtracking(candidates, target, [], 0)
        return self.res
        
    def backtracking(self, candidates, target, path, start_index):
        if target == 0:
            # print(path)
            self.res.append(path[:])
            return 
        if target < 0: return 


        for i in range(start_index, len(candidates)):
            if target-candidates[i] < 0:
                continue
            path.append(candidates[i])
            self.backtracking(candidates, target-candidates[i], path, i)
            path.pop()

40.组合总和II

1. 相比于之前这个题的区别，就是这个在candidates里可以重复，但是最后res里不能有重复的list。想要去重还挺难想的，不过题解里给了一个思路，就是在树的同一层进行操作，即可进行去重操作。递归的时候不在树的同一层，因此不需要有去重操作。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        candidates.sort()
        self.backtracking(candidates, target, 0, [])
        return self.res

    def backtracking(self, candidates, target, start_index, path):
        if target == 0:
            
            self.res.append(path[:])
            return
        for i in range(start_index, len(candidates)):
            if target-candidates[i] < 0: continue   # 剪枝
            # 树的同一层，如果有重复的，跳过
            if candidates[i] == candidates[i-1] and i > start_index: continue

            path.append(candidates[i])
            self.backtracking(candidates, target-candidates[i], i+1, path)
            path.pop()

131.分割回文串

1. 这题好难。。没有思路。。根本想不到分割和回溯又什么关系。所以直接看的题解。可能需要复习复习。
2. 题解给的解释：
   - 递归用于纵向遍历
   - for循环用于横向遍历
   - 当切割线迭代至字符串末尾，说明找到一种方法
   - 类似组合问题，为了不重复切割同一位置，需要start_index来做标记下一轮递归的起始位置(切割线)
   - 关于模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.res = []
        self.backtracking(s, 0, [])
        return self.res

    def backtracking(self, s, start_index, path):
        if start_index == len(s):
            self.res.append(path[:])
            return 
        
        for i in range(start_index, len(s)):  # 用start_index作为分割点
            if self.is_palindrome(s, start_index, i):
                path.append(s[start_index:i+1])
                self.backtracking(s, i+1, path)
                path.pop()
        

    def is_palindrome(self, s, start, end):
        i = start
        j = end
        while(i < j):
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

# 若反序和正序相同，意味着这是回文串
if s[start_index: i + 1] == s[start_index: i + 1][::-1]: