代码随想录学习Day 23

39.组合总和

题目链接

讲解链接

本题与前面几道组合问题的主要差别在于数组中的元素可以重复使用 ，所以在回溯函数的for循环处starrtindex的设置是重点。

回溯三部曲：

1.递归函数参数及返回值：参数就是题目中给出的candidates数组和目标和target以及确定每一轮循环开始位置的startindex，不需要返回值。

def backtracking(self, startindex, candidates, target):

2.递归终止条件：当到达叶子节点，即sum>target或者sum==target时递归终止。当大于时直接返回，等于时将path添加到结果集中。

if sum(self.path) > target:
    return
if sum(self.path) == target:
    self.result.append(self.path[:])
    return

3.单层递归逻辑：单层for循环依然是从startIndex开始，搜索candidates集合。重点在于本题中元素是可以重复选取的。所以在递归调用自身时，startindex的选择不能是+1，而是要选择当前的i值，这样才能实现重复选取元素，并且不会出现重复的组合。

for i in range(startindex, len(candidates)):
    if sum(self.path) + candidates[i] > target:
        continue
    self.path.append(candidates[i])
    self.backtracking(i, candidates, target)
    self.path.pop()

 整体代码如下：

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
    def backtracking(self, startindex, candidates, target):
        if sum(self.path) > target:  # 大于直接返回
            return
        if sum(self.path) == target:  # 等于则加入result
            self.result.append(self.path[:])
            return
        for i in range(startindex, len(candidates)):
            if sum(self.path) + candidates[i] > target:  # 剪枝操作，当前和加上数组中第i个值如果已经大于target，那么就不需要再遍历后面的部分，直接continue即可
                continue
            self.path.append(candidates[i])
            self.backtracking(i, candidates, target)  # 从i开始
            self.path.pop()
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates = sorted(candidates)
        self.backtracking(0, candidates, target)
        return self.result

40.组合总和Ⅱ

题目链接

讲解链接

难点：本题candidates 中的每个数字在每个组合中只能使用一次。本题数组candidates的元素是有重复的，而之前的题目则是无重复元素的数组candidates，并且解集中不能包含重复的元素。

元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

树层去重的话，需要对数组排序！树形结构如图所示：

 回溯三部曲：

1.递归函数参数及返回值：除了candidates、target和startindex之外，还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

def backtracking(self, candidates, target, startindex, used):

2.确定终止条件：当sum>target或sum==target时返回。

if sum(self.path) > target:
    return
if sum(self.path) == target:
    self.result.append(self.path[:])
    return

3.单层递归逻辑：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过，就需要借助used数组进行判断

如果candidates[i]==candidates[i-1]并且used[i-1]==false，就说明前一个树枝，使用了candidates[i-1]，也就是说同一树层使用过candidates[i-1]。此时for循环里就应该continue.

for i in range(startindex, len(candidates)):
    if i > startindex and candidates[i] == candidates[i - 1] and not used[i - 1]:
    continue
    if sum(self.path) + candidates[i] > target:
    break
    self.path.append(candidates[i])
    used[i] = True
    self.backtracking(candidates, target, i + 1, used)
    used[i] = False
    self.path.pop()

使用used数组做标记的整体代码如下： 

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
    def backtracking(self, candidates, target, startindex, used):
        if sum(self.path) == target:
            self.result.append(self.path[:])
            return
        for i in range(startindex, len(candidates)):
            if i > startindex and candidates[i] == candidates[i - 1] and not used[i - 1]:
                continue
            if sum(self.path) + candidates[i] > target:
                break
            self.path.append(candidates[i])
            used[i] = True
            self.backtracking(candidates, target, i + 1, used)
            used[i] = False
            self.path.pop()
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return None
        used = [False] * len(candidates)
        self.backtracking(sorted(candidates), target, 0, used)
        return self.result

 但本题中used数组只是为了更好的理解回溯过程，其实可以省去。因为对数组进行过排序，那么只需要判断i > startindex并且candidates[i] == candidates[i-1]，就说明前一个同样的元素已经被使用过了，当前元素的处理可以直接跳过来实现去重。

class Solution:
    def __init__(self):
        self.path = []  # 保存单个结果
        self.result = []  # 保存结果集
    def backtracking(self, candidates, target, startindex):
        if sum(self.path) == target:  # 和等于target，则将其加入结果集中
            self.result.append(self.path[:])
            return
        for i in range(startindex, len(candidates)):
            if i > startindex and candidates[i] == candidates[i - 1]:  # 在for循环中实现去重，重复出现的只保留最左侧的一支树枝，其他的就去重
                continue
            if sum(self.path) + candidates[i] > target:  # 剪枝操作，当前和+c[i]大于目标就直接跳出，不需要进行后续的遍历
                break
            self.path.append(candidates[i])  # 处理节点
            self.backtracking(candidates, target, i + 1)  # 递归
            self.path.pop()  # 回溯操作
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return None
        self.backtracking(sorted(candidates), target, 0)  # 要先对数组进行排序才能实现去重
        return self.result

131.分割回文串

题目链接

讲解链接

思路：首先需要考虑两个问题，怎样进行切割、怎样判断是否回文。切割问题类似组合问题，同样可以抽象为树形结构，切割到字符串的末尾位置，就说明找到了一个解。

 回溯三部曲：
1.递归函数参数及返回值：参数必须要有的就是字符串s和用于确定切割位置的startindex，除此之外还需要两个全局变量来保存结果。

def backteracking(self, s, startindex):

2.递归终止条件：当切割到了字符串的末尾，也就是startindex的值与字符串的长度相等时，说明已经找到了一组分割的方案。

if startindex == len(s):
    self.result.append(self.path[:])
    return

3.单层递归逻辑：在for循环中，起始位置为startindex，那么要截取的部分就是[startindex, i]。然后先判断这个字串是不是回文，是则将其加入path中，不是则直接返回进行下一次递归。

for i in range(startindex, len(s)):
    if self.isPalindrome(s, startindex, i):
        self.path.append(s[startindex:i+1])
        self.backteracking(s, i + 1)
        self.path.pop()

整体代码如下：

class Solution:
    def __init__(self):
        self.path = []  # 保存单个回文字串
        self.result = []  # 保存结果集
    def isPalindrome(self, s, left, right):  # 判断是否为回文字串
        while left < right:  # 双指针法
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    def backteracking(self, s, startindex):
        if startindex == len(s):  # 终止条件，当切割位置到了字符串末尾，则说明已经找到了一个解
            self.result.append(self.path[:])
            return
        for i in range(startindex, len(s)):
            if self.isPalindrome(s, startindex, i):  # 判断startindex到i之间的部分是否为回文串
                self.path.append(s[startindex:i+1])  # 将符合条件的结果加入path中
                self.backteracking(s, i + 1)  # 从下一层开始递归
                self.path.pop()  # 回溯
    def partition(self, s: str) -> List[List[str]]:
        self.backteracking(s, 0)
        return self.result