Problem P32. [算法课分支限界法]Partition to K Equal Sum Subsets

纯暴力遍历+剪枝，将任务看出有k个桶，要将每个桶都刚刚好装满。

#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
#include<string>

using namespace std;

static bool dfs(vector<int>& nums, int cur, vector<int>& arr, int k) {
    //已经遍历到了-1说明前面的所有数都正好可以放入桶里，那所有桶的值此时都为0，说明找到了结果，返回true
    if (cur < 0){
        return true;
    }
    // 遍历 k 个桶
    for (int i = 0; i < k; i++){
        if (i && arr[i] == arr[i-1]) {
            continue;
        }
        // 如果正好能放下当前的数或者放下当前的数后，还有机会放前面的数（剪枝）
        if (arr[i] == nums[cur] || (cur > 0 && arr[i] - nums[cur] >= nums[0])){
            // 放当前的数到桶i里
            arr[i] -= nums[cur];
            // 开始放下一个数
            if (dfs(nums, cur-1, arr, k)){
                return true;
            }
            // 这个数不放在桶i里
            arr[i] += nums[cur];
        }
    }
    return false;
}
static bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0){
        return false;
    }
    int per = sum / k;
    sort(nums.begin(), nums.end());
    if (nums.back() > per){
        return false;
    }
    // 建立一个长度为 k 的桶, 桶里的每个值都是子集的和
    vector<int> arr = vector<int>(k, per);
    // 从数组最后一个数开始进行递归
    return dfs(nums, nums.size()-1, arr, k);
}
int main()
{
    vector<int> nums;
    int k;
    while (1){
        int d;
        int ret = scanf("%d", &d);
        if (ret == EOF){
            break;
        }
        nums.push_back(d);
    }
    k = nums.back();
    nums.pop_back();
    if (canPartitionKSubsets(nums, k)){
        cout << "true";
    }else {
        cout << "false";
    };
    return 0;
}