数据结构之回溯

回溯思想作为最常见算法思维之一，在数据结构中也常常使用。除了三大常用的算法思维（递归、动态规划、回溯）。
一般还包括二分查找、快慢指针、左右指针、滑动窗口、前缀和数组、差分数组。只是后面的几种不太常见而已。

回溯解题思路三件套

1. 路径：也就是已经做出的选择。
2. 选择列表：也就是你当前可以做的选择。
3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法使用时还需要递归思路辅助

回溯算法较其他两种算法思维更好理解，常用的技巧也不太复杂。因此只讲解一个实例。

代码框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心套路就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。

集合划分： 排列组合问题

问题描述： 在给定的集合中，划分等和的n等分。

解题代码：

def canPartitionKSubsets(nums: list, k: int):
        if (k > len(nums)):
            return False
        num_sum = 0
        for v in nums:
            num_sum += v
        if (num_sum % k != 0):
            return False
        bucket = [0 for _ in range(k)]
        target = int(num_sum / k)
        return backtrack(nums, 0, bucket, target)

    def backtrack(nums, index, bucket, target):
        # 检查所有的划分是否相等
        if (index == len(nums)):
            i = 0
            while i < len(bucket): 
                if (bucket[i] != target):
                    return False
                i += 1
            return True

        i = 0
        while i < len(bucket): 
            ## 细节处理重点
            if (bucket[i] + nums[index] > target):
                i += 1  
                continue
            ## 回溯算法核心思想
            bucket[i] += nums[index]
            if (backtrack(nums, index + 1, bucket, target)):
                return True
            bucket[i] -= nums[index]
            i += 1 
        return False