Medium

题目描述

给定一个整数数组 nums 和一个整数 k，如果可以将这个数组分成 k 个非空子集，使得每个子集的元素和都相等，则返回 true。

示例 1:

输入: nums = [4,3,2,3,5,2,1], k = 4
输出: true
解释: 可以将其分成 4 个子集 (5), (1, 4), (2,3), (2,3)，每个子集的和都是 5。

示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false

约束条件:

  • 1 <= k <= nums.length <= 16
  • 1 <= nums[i] <= 10^4
  • 每个元素的频率在 [1, 4] 范围内。

解题思路

解题思路

这是一个经典的回溯问题。核心思想是将数组分成k个和相等的子集。

预处理检查：

  1. 计算数组总和，如果不能被k整除，直接返回false
  2. 目标子集和 = 总和 / k
  3. 如果存在任何元素大于目标和，返回false

两种主要解法：

  1. 按元素分配（推荐）：遍历每个元素，尝试将其放入k个桶中的某一个
  2. 按桶填充：依次填充k个桶，每个桶尝试所有可能的元素组合

优化策略：

  • 将数组降序排列，优先处理大数字，减少搜索空间
  • 使用visited数组避免重复使用元素
  • 剪枝：如果当前桶的和加上当前元素超过目标值，跳过

按元素分配的方法更高效，因为它避免了重复的子集组合。时间复杂度为O(k^n)，其中n是数组长度。

代码实现

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        
        int target = sum / k;
        sort(nums.rbegin(), nums.rend());
        
        if (nums[0] > target) return false;
        
        vector<int> buckets(k, 0);
        return backtrack(nums, buckets, 0, target);
    }
    
private:
    bool backtrack(vector<int>& nums, vector<int>& buckets, int index, int target) {
        if (index == nums.size()) {
            return true;
        }
        
        for (int i = 0; i < buckets.size(); i++) {
            if (buckets[i] + nums[index] <= target) {
                buckets[i] += nums[index];
                if (backtrack(nums, buckets, index + 1, target)) {
                    return true;
                }
                buckets[i] -= nums[index];
            }
            
            // 剪枝：如果当前桶为空，后续的空桶也会失败
            if (buckets[i] == 0) break;
        }
        
        return false;
    }
};

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total = sum(nums)
        if total % k != 0:
            return False
        
        target = total // k
        nums.sort(reverse=True)
        
        if nums[0] > target:
            return False
        
        buckets = [0] * k
        
        def backtrack(index):
            if index == len(nums):
                return True
            
            for i in range(k):
                if buckets[i] + nums[index] <= target:
                    buckets[i] += nums[index]
                    if backtrack(index + 1):
                        return True
                    buckets[i] -= nums[index]
                
                # 剪枝：如果当前桶为空，后续的空桶也会失败
                if buckets[i] == 0:
                    break
            
            return False
        
        return backtrack(0)

public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int sum = nums.Sum();
        if (sum % k != 0) return false;
        
        int target = sum / k;
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        
        if (nums[0] > target) return false;
        
        int[] buckets = new int[k];
        return Backtrack(nums, buckets, 0, target);
    }
    
    private bool Backtrack(int[] nums, int[] buckets, int index, int target) {
        if (index == nums.Length) {
            return true;
        }
        
        for (int i = 0; i < buckets.Length; i++) {
            if (buckets[i] + nums[index] <= target) {
                buckets[i] += nums[index];
                if (Backtrack(nums, buckets, index + 1, target)) {
                    return true;
                }
                buckets[i] -= nums[index];
            }
            
            // 剪枝：如果当前桶为空，后续的空桶也会失败
            if (buckets[i] == 0) break;
        }
        
        return false;
    }
}

var canPartitionKSubsets = function(nums, k) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum % k !== 0) return false;
    
    const target = sum / k;
    nums.sort((a, b) => b - a);
    
    if (nums[0] > target) return false;
    
    const used = new Array(nums.length).fill(false);
    
    function backtrack(start, k, currentSum) {
        if (k === 1) return true;
        if (currentSum === target) {
            return backtrack(0, k - 1, 0);
        }
        
        for (let i = start; i < nums.length; i++) {
            if (used[i] || currentSum + nums[i] > target) continue;
            
            used[i] = true;
            if (backtrack(i + 1, k, currentSum + nums[i])) {
                return true;
            }
            used[i] = false;
            
            if (currentSum === 0) break;
        }
        
        return false;
    }
    
    return backtrack(0, k, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k^n)最坏情况下每个元素都要尝试放入k个桶中
空间复杂度O(k + n)递归栈深度O(n)，桶数组O(k)

相关题目