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

本文主要是介绍【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.resdef 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:continuepath.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.resdef backtracking(self, candidates, target, start_index, path):if target == 0:self.res.append(path[:])returnfor i in range(start_index, len(candidates)):if target-candidates[i] < 0: continue   # 剪枝# 树的同一层，如果有重复的，跳过if candidates[i] == candidates[i-1] and i > start_index: continuepath.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.resdef 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 = startj = endwhile(i < j):if s[i] != s[j]:return Falsei += 1j -= 1return True

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

这篇关于【leetcode刷刷】39. 组合总和、40.组合总和II、131.分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---