Leetcode 【216、769】
题目描述：【DFS】216. Combination Sum III
解题思路：
这道题一看要求输出所有满足题意的组合，很明显 DFS 回溯法进行求解，属于模板题。不过这倒题需要注意几个剪枝情况：
- 因为是组合数，所以保证后一个数比前一个数大即可；
- 当深度小于 k 时才进行深搜，深度大于 k 没必要深搜。
Python3 实现：
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def search(r, tar): # tar为目标值
for i in range(1, 10):
if self.b[i] == False and i > self.a[r-1]:
self.a[r] = i
self.b[i] = True
tar -= i # 目标值减小
if r == k and tar == 0: # 找到一组解
self.ans.append([])
for j in range(1, k+1):
self.ans[-1].append(self.a[j])
elif r < k: # 深度小于k才进行深搜
search(r+1, tar)
self.b[i] = False # 恢复b[i]为False
tar += i # 恢复目标值tar
self.ans = [] # 保存所有答案
self.a = [0] * 10 # 保存一组答案
self.b = [False] * 10 # 标记数字i是否被使用过
search(1, n) # 调用深搜算法
return self.ans题目描述：【Array】769. Max Chunks To Make Sorted
解题思路：
方法1（普通的方法）：
- 因为要保证有序，所以简单想法就是先找 0 的位置，判断 0 左右两边的序列排序后是否满足升序。如果不满足，就找 1、2, ... 的位置，满足的话就划分出一个块，然后标记当前划分的位置。
- 当前划分的位置能保证左侧是一个块，但是右侧还可以继续划分。
- 所以，继续找下一个在划分位置右侧的数字，然后按照第一步相同的思路做，直到所有数字找完为止。
举例：arr = [2,0,3,1,5,4,6]，刚开始找到 0 的位置，发现 [2,0] 和 [3,1,5,4,6] 不满足；找 1 的位置，发现 [2,0,3,1] 和 [5,4,6] 满足，块数加 1；找 2、3，由于都在划分处（1 的位置）的左侧，不用管；找 4 的位置，在划分位置的右侧，[5 4] 和 [6] 满足，块数加 1；找 5，由于都在划分处（4 的位置）的左侧，不用管；找 6，在划分位置的右侧，[6] 和 [] 满足，块数加 1；最后得到结果为 3。
Python3 实现：
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
N = len(arr)
sort = [i for i in range(N)]
chunks = sort_len = i = 0
split = -1 # 划分处
while i < N: # 找每个数字
ind = arr.index(i) # 每个数字的位置
if ind < split: # 在划分处左侧的数字，不用管
i += 1
continue
left, right = arr[split+1:ind+1], arr[ind+1:] # 划分成左右两个序列
left.sort()
right.sort()
if left + right == sort[sort_len:]:
chunks += 1
sort_len += len(left)
split = ind # 更新划分处的位置
i += 1
return chunks方法2（巧妙的方法）：
其实有一种巧妙的方法。假设原序列进行了一种划分，不管如何分，第一组排序完都为 0,1, 2, ..., k ，不难发现，原序列切割的那个点的前面必须要出现 0,1,2, ..., k。
因为数组的排序后正确顺序应该是 arr[i] 处的数是 i。所以，从头遍历数组，每次更新最大值 max_，即 max_ = max(max_, arr[i])，max_ 必须在 i 处才能满足对 0～i 数字排序后能够恰好是正确的位置。因为 max_ 是第 0～i 个数字中的最大值，遍历的过程中如果 max_ == i，就保证了前面 i-1 个数字必然都比 max_ 小（因为 max_ 是 0～i 中的最大值），则第 0～i 个数字必然能排列成正确顺序，就能划分成一个块。继续遍历，找到下一个满足 max_ == i 的地方（记为 j），则 i+1～j 又能分为一个块。以此类推，直到遍历到最后一个数为止得到答案。
简单一句话来说，当前最大值与下标 i 相等时，前面就可以划分成一个块。
举例：arr = [2,0,3,1,5,4,6]，刚开始 max_ = 2，说明至少需要遍历到 i == 2 才可能划分成一个块（因为要包括 0 ~2）。遍历到 3 时，max_ 就要改写成 3，说明至少需要遍历到 i == 3 才可能划分成一个块（因为要包括 0~3）。到了 i == 3，发现刚好满足条件，则块数加 1。继续遍历，max_ = 5，并且能到 i == 5，块数加 1。最后，max_ = 6，并且 i == 6，块数加 1，最后得到结果 3。
Python3 实现：
class Solution:
def maxChunksToSorted(self, arr: List[int]) -> int:
cnt = max_ = 0
for i in range(len(arr)):
max_ = max(max_, arr[i]) # 每次都更新最大值
if max_ == i: # 最大值与下标相等，说明可以划分成一个块
cnt += 1
return cnt腾讯云开发者
