698 划分为k个相等的子集（dfs减枝）

落日映苍穹つ 2022-09-03 11:22 100阅读 0赞

**1. 问题描述：**

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

**示例 1：**

输入： nums = \[4, 3, 2, 3, 5, 2, 1\], k = 4  
输出： True  
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

**提示：**

1 <= k <= len(nums) <= 16  
0 < nums\[i\] < 10000  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets

**2. 思路分析：**

这道题目与力扣[473][]题火柴剪正方形考察的本质是一样的，这道题目是让我们判断是否可以划分为k个集合，473题是让我们判断是否可以划分为4个集合，都是非常经典的**搜索减枝**问题，而且在很多场景中都会遇到这一类的问题，我们可以记住其中涉及到的剪枝技巧，当我们遇到类似题目的时候就可以使用这些技巧进行剪枝。首先搜索的策略是每个集合每个集合这样凑，也即当我们凑好了一个集合之后那么凑下一个集合，搜索的过程中主要包含以下几个减枝：

*  在搜索之前我们可以对nums从大到小排序，这样每一次搜索的分支是比较少的，可以避免从小的数字搜索到比较多的分支的情况
 *  因为nums是排好序的，所以我们在凑每个集合的时候按照下标递增的顺序进行搜索，这样可以避免搜索重复的情况，例如1，3，2与1，2，3的集合是一样的我们只需要搜索一次就可以了
 *  当某个集合凑的数字失败了主要分为以下几种情况的减枝：

1.  当前数字后面有多个相同的数字，那么可以使用循环跳过当前位置后面与当前数字相同的数字，因为当前数字都不成功了相同的数字也不可能在当前这个集合中凑成功的
2.  当前数字属于集合中的第一个数字，那么直接返回False即可，因为如果当前第一个数字在其他集合中凑成功了那么说明当前数字在其他集合中也属于第一个数字（在凑每一个集合的时候都是从下标最小且未使用过的数字进行搜索的）所以与之前凑不成功就矛盾了
3.  当前的数字属于最后一个数字，那么直接返回False即可，与当前数字是集合中的第一个数字的情况是类似的，如果当前这个数字使用其他若干个数字成功了那么我们可以交换当前这个集合中的若干个数字与之前没有凑成功的最后一个数字之后发现是可以凑成功的，所以与之前凑不成功也矛盾了

所以我们在搜索的时候对上面几种情况进行剪枝即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # start表示当前nums递归的位置, cur表示当前这个集合的总和, s表示每个集合需要凑成的总和, count表示当前是第几个集合, sta是标记列表标记哪些数字已经被使用过了
        def dfs(self, k: int, start: int, cur: int, s: int, count: int, sta: List[int], nums: List[int]):
            if count == k: return True
            # 凑好了当前的集合那么凑下一个集合, 并且从第一个位置开始凑
            if cur == s: return self.dfs(k, 0, 0, s, count + 1, sta, nums)
            # 每个集合按照递增的顺序进行递归
            i = start
            while i < len(nums):
                if sta[i] == 1:
                    i += 1
                    continue
                # 只有当当前的总和小于s的时候才往下递归, 因为这个时候这个数字才是合法的
                if cur + nums[i] <= s:    
                    # 标记当前的数已经使用过了
                    sta[i] = 1
                    if self.dfs(k, i + 1, cur + nums[i], s, count, sta, nums): return True
                    # 回溯
                    sta[i] = 0
                    # 回溯到这里说明是失败了所以判断当前是否第一根还是最后一根, 如果满足直接返回False
                    if cur == 0 or cur + nums[i] == s: return False
                i += 1
                # 失败了那么需要跳过当前所有相等的数字
                while i < len(nums) and nums[i] == nums[i - 1]: i += 1
            return False
    
        # 经典的dfs减枝的问题
        def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
            # 首先从大到小排序这样可以避免搜索的时候存在很多分支, 这样选择的数量是不多的
            nums.sort(reverse=True)
            n = len(nums)
            sta = [0] * n
            s = sum(nums)
            # 不能够整除肯定无解
            if s % k: return False
            return self.dfs(k, 0, 0, s // k, 0, sta, nums)

[473]: https://blog.csdn.net/qq_39445165/article/details/118583744