礼品派发

[题目链接](https://www.nowcoder.com/practice/f19531dcc5e243b98a9826ee8849cfd2)

思路

本题是经典的 K 等和子集划分 问题：给定一组礼品价格和粉丝人数 $k$ ，判断能否将所有礼品分成 $k$ 组，使每组价格之和相等。

回溯 + 剪枝

基本判断：若总价格不能被 $k$ 整除，直接返回 false。每组的目标价格为 $target = sum / k$ 。

降序排序：将价格从大到小排序，这样能更早触发剪枝（大的放不下就提前回退）。

回溯搜索：维护 $k$ 个桶，依次尝试将每个礼品放入某个桶，若桶内累加值不超过 $target$ 就递归下一个礼品。

关键剪枝：

- 如果当前桶的值和之前某个桶相同，跳过（去重，避免等价搜索分支）。

- 如果某个空桶放入当前礼品后仍无法成功，不必再尝试其他空桶（所有空桶等价）。

样例验证

[5,4,1,3,2,3,2], k=4：总和 20， $target=5$ 。可分为 $(5), (4,1), (3,2), (3,2)$ ，返回 true。
[1,2,2,2,2], k=3：总和 9， $9 \bmod 3 = 0$ ， $target=3$ 。但无法找到 3 组和为 3 的划分，返回 false。

代码

C++
Java

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canEqualDistribution(vector<int>& prices, int k) {
        int sum = 0;
        for (int p : prices) sum += p;
        if (sum % k != 0) return false;
        int target = sum / k;

        sort(prices.begin(), prices.end(), greater<int>());
        if (prices[0] > target) return false;

        vector<int> buckets(k, 0);
        return dfs(prices, buckets, 0, target);
    }

    bool dfs(vector<int>& nums, vector<int>& buckets, int idx, int target) {
        if (idx == (int)nums.size()) return true;

        vector<bool> tried(target + 1, false);
        for (int i = 0; i < (int)buckets.size(); i++) {
            if (buckets[i] + nums[idx] > target) continue;
            if (tried[buckets[i]]) continue;
            tried[buckets[i]] = true;

            buckets[i] += nums[idx];
            if (dfs(nums, buckets, idx + 1, target)) return true;
            buckets[i] -= nums[idx];

            if (buckets[i] == 0) break;
        }
        return false;
    }
};

import java.util.*;

public class Solution {
    public boolean canEqualDistribution(int[] prices, int k) {
        int sum = 0;
        for (int p : prices) sum += p;
        if (sum % k != 0) return false;
        int target = sum / k;

        Integer[] nums = new Integer[prices.length];
        for (int i = 0; i < prices.length; i++) nums[i] = prices[i];
        Arrays.sort(nums, Collections.reverseOrder());
        if (nums[0] > target) return false;

        int[] buckets = new int[k];
        return dfs(nums, buckets, 0, target);
    }

    private boolean dfs(Integer[] nums, int[] buckets, int idx, int target) {
        if (idx == nums.length) return true;

        boolean[] tried = new boolean[target + 1];
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] + nums[idx] > target) continue;
            if (tried[buckets[i]]) continue;
            tried[buckets[i]] = true;

            buckets[i] += nums[idx];
            if (dfs(nums, buckets, idx + 1, target)) return true;
            buckets[i] -= nums[idx];

            if (buckets[i] == 0) break;
        }
        return false;
    }
}

复杂度分析

时间复杂度：最坏 $O(k^n)$ ，其中 $n$ 是礼品数量。但通过排序和剪枝，实际运行远快于此。
空间复杂度： $O(n + k)$ ，递归栈深度 $O(n)$ ，桶数组 $O(k)$ 。