• 任务
  • 39. 组合总和
    • 思路
  • 40. 组合总和II
    • 思路
  • 131. 分割回文串
    • 思路
• 心得体会

任务

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

思路

回溯问题的关键是抽象出正确的多叉树结构，对于本题要求，每一层是一次选择，第一层就是第一次选择，后续递归中，为了避免重复，遍历自己之后的元素。这种问题最好举例描述比较清晰，下面给出例子。
数组为[2,3,6,7],target为7。我们构造一颗树，其中的某条路径表示每次的选取数值，由于题目说同一个数字可以无限制重复选取，因此上次选取后，下次还可以选，所以递归区间[start,end)，但是避免顺序不同的重复组合，（比如选了2,2,3，下次选了3,2,2），所以，我只能选我及我后面的元素。显然，我们不可能无限递归（无限选取）下去，何时终止呢？实际上，只要当前路径累积的值等于target或大于target就说明可以停止了（数组元素为正数）。
由于宽度限制，这张图没有给出后续的过程，比如其中一条符合的路径 2 2 3.

class Solution:
    def __init__(self):
        self.path = []
        self.paths = []
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.dfs(candidates,target,0)
        return self.paths
   
    def dfs(self,candidates,target,index): # 每层只选自己和自己之后的元素
        if target < 0: return
        if target == 0:
            self.paths.append(self.path[:])
            return
        
        size = len(candidates)
        for i in range(index,size):
            target -= candidates[i]
            self.path.append(candidates[i])
            self.dfs(candidates,target,i)
            self.path.pop()
            target += candidates[i]     

40. 组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。

思路

注意和上题的不同之处，这题的要求是每个数只能使用一次，且数字相同的数可以都使用。为树枝剪枝，考虑只有重复数的第一个节点出现时才采取，使用i或者代码随想录中思路中的used数组均可实现。

#解法1
class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        self.dfs(candidates,target,0)
        return self.paths

    def dfs(self,candidates,target,start): # start每层只选自己之后和自己不同的的元素
        if target < 0: return
        if target == 0:
            self.paths.append(self.path[:])
            return
        
        size = len(candidates)
        for i in range(start,size):
            if i > start and candidates[i] == candidates[i-1]:
                continue
            target -= candidates[i]
            self.path.append(candidates[i])
            self.dfs(candidates,target,i+1)
            self.path.pop()
            target += candidates[i]    

##解法2
class Solution:
    def __init__(self):
        self.path = []
        self.paths = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        used = [False]* len(candidates)
        self.dfs(candidates,target,0,used)
        return self.paths

    def dfs(self,candidates,target,start,used): # start每层只选自己之后和自己不同的的元素
        if target < 0: return
        if target == 0:
            self.paths.append(self.path[:])
            return
        
        size = len(candidates)
        for i in range(start,size):
            if i > 0 and not used[i-1] and candidates[i] == candidates[i-1]:
                continue
            used[i] = True
            target -= candidates[i]
            self.path.append(candidates[i])
            self.dfs(candidates,target,i+1,used)
            self.path.pop()
            target += candidates[i]   
            used[i] = False  

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串。返回 s 所有可能的分割方案。

思路

本题的思路较难，需要将每层分割抽象成[start,end)，
比如 第一次分割可选 [0,end）中的位置，那么在第一次分割选了0位置的情况下，第二次可选[1,end)中的位置。。。
路径应该加字符串的哪些部分是个难点,考虑任意单层递归，[start,i+1)是我们所需的区间。
比如最上层循环，选取[0,end)位置 ，start就是0 ，end为实际选取了哪个节点（的哨兵，因为闭区间），因为回溯后，该层的i变量也会正常遍历，不受其他层影响。
此时我们第x层的某个节点的字符串表示，我们当前第x次选的分割为当前节点所需要的sub字符串.例如，当x=1时,选1这个节点（第一层第二个节点），表示我们第一次选的分割为1时，sub字符串区间为[0,2)，然后在每层累加字符串。返回条件是分割索引已经到最后。
实际是在叶子节点的后面虚拟节点返回的。
按照遍历序，先到左下，然后start为len(s)退出，返回叶子层，然后进行当前节点父节点的孩子这一层的循环，再返回父节点，继续循环。。

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

    def partition(self, s: str) -> List[List[str]]:
        self.dfs(s,0)
        return self.paths
    def dfs(self,s,start):
        if len(s) == start:
            self.paths.append(self.path[:])
        
        for i in range(start,len(s)):
            if self.isPal(s,start,i+1):
                self.path.append(s[start:i+1])
                self.dfs(s,i+1)
                self.path.pop()
    def isPal(self,s,start,end):
        return s[start:end] == s[start:end][::-1]

心得体会

对于前两题可以思考后理解并写出，对于最后一题只能懵懵懂懂的写出，写出后可以理解整个树的处理过程，对于[start:i+1)的思考，试试只考虑单层递归应该比较好理解，对于树的遍历的全部逻辑是写完后分析细节用的，对于题目应该试着去用单层递归的思路去做（包括之前的组合问题），后续需要再做一次关于分割的题。