组合总和

原始版本

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def backtracking(self,candidates,target,sums,index,path,result):
        if sums > target:
            return
        if sums == target:
            result.append(path[:])
            return #空返回，改变result就行

        for i in range(index,len(candidates)):
            sums += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates,target,sums,i,path,result)
            sums -= candidates[i] 
            path.pop()
        
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        self.backtracking(candidates,target,0,0,[],result)
        return result

总的来说，就是回溯的模板，只是在递归的过程中，需要判断一下是否超过了目标值，如果超过了，就直接返回。如果等于目标值，就将当前路径加入结果集中。然后因为可以重复使用元素，所以递归的索引从当前索引开始（不用i+1）。

排序加剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def backtracking(self,candidates,target,sums,index,path,result):
        if sums == target:
            result.append(path[:])
            return #空返回，改变result就行

        for i in range(index,len(candidates)):
            sums += candidates[i]
            if sums > target:
                break
            path.append(candidates[i])
            self.backtracking(candidates,target,sums,i,path,result)
            sums -= candidates[i] 
            path.pop()
        
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.backtracking(candidates,target,0,0,[],result)
        return result

组合总和II

40. 组合总和 II

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def backtracking(self,candidates,target,sums,index,used,path,result):
        if sums == target:
            result.append(path[:])
            return 
        for i in range(index,len(candidates)): #用循环让数组的每个变成一棵树的根节点，同时一棵树比一颗更窄，目的就是不要重复（指的是（1，2）（2，1）这种）
            #下面的去重是数组里面本身元素的重复导致的（但是又不能简单的把数组元素去重）
            if i>index and candidates[i] == candidates[i-1] and not used[i-1]: #进行层剪枝的操作
                continue
            sums += candidates[i]
            if sums > target:
                break
            path.append(candidates[i])
            used[i] = True
            self.backtracking(candidates,target,sums,i+1,used,path,result)
            used[i] = False
            sums -= candidates[i]
            path.pop()

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

这道题关键在于区分树枝重复和树层重复，叶子可以和父节点相同，但是不能跟兄弟相同（包括每一个根节点）

分割回文串

131. 分割回文串

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def backtracking(self,s,index,path,result):
        if index == len(s):
            result.append(path[:])
            return 
        for i in range(index,len(s)):
            if s[index:i+1] == s[index:i+1][::-1] :
                path.append(s[index:i+1])
                self.backtracking(s,i+1,path,result)
                path.pop()
    def partition(self, s: str) -> List[List[str]]:
        result = []
        self.backtracking(s,0,[],result)
        return result

就是用递归加回溯把所有切割方式列出来返回是回文的内容