题解 | #数组分解K个等和子数组#

该题涉及的细节较多，采用的多种优化方法，具体可参见具体代码。同时该题的输入为一个字符串需要一定的字符串分割处理能力。该题的大致思路是将数组中的n个元素视为小球，小球有质量nums[i]。k个子集视为盒子，每个盒子必须装质量恰好为target的小球。对于每个盒子来说每个小球共有两种状态“装入”或“不装入”该盒子。当一个盒子满足装质量恰好为target的小球时，开始装下一个盒子，直到需要装的盒子数为0.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<int, bool> memo;
bool backtrack(int k, int sum, vector<int>& nums, int start, int used, int target)
{
    if(k == 0)     //k = 0时，所有的子集和都等于target了返回true.
    return true;
    if(sum == target)
    {
        bool res = backtrack(k - 1, 0, nums, 0, used, target); //装好一个子集准备装下一个。
        memo[used] = res;   //优化遍历方法，避免重复计算
        return res;
    }
    if(memo.count(used))
    return memo[used];
    for(int i = start; i < nums.size(); ++i)
    {
        if(used & (1 << i))   //状态压缩下的去除操作
        continue;
        sum += nums[i];
        used |= (1 << i);   //将used的第i位置为1,代表nums[i]已经被使用
        if(backtrack(k, sum, nums, i + 1, used, target)) //如果选择将nums[i]加入当前子集能成功完成将数组分解K个等和子数组，直接返回true，不必再进行循环。
        return true;
        used ^= (1 << i);
        sum -= nums[i];
    }
    return false;  //遍历所有元素加入当前子集不能完成将数组分解K个等和子数组，返回false。
}

int main() {
    string str;
    vector<int> ivec;
    getline(cin, str);
    int n = str.size();
    int k;
    int sign;
    for(int i = 0; i < n; ++i)    //将输入的字符串进行处理
    {
        if(str[i] == ';')
        {
            sign = i;
            break;
        }
    }
    string s1 = str.substr(1, sign - 1);
    string s2 = str.substr(sign + 1, n - sign - 1);
    k = stoi(s2);
    int front = 0;
    int end = 0;
    while(end < s1.size())
    {
        if(s1[end] != ',' && s1[end] !=']')
        ++end;
        else
        {
            string ss = s1.substr(front, end - front);
            ivec.push_back(stoi(ss));
            ++end;
            front = end;
        }
    }
    if(k > ivec.size())  //减枝操作，当需要分的子集数大于整个数组的数字总数返回false。
    {
        cout << "False";
        return 0;
    }
    
    int sum = 0;
    for(int i = 0; i < ivec.size(); ++i)
    {
        sum += ivec[i];
    }
    if(sum % k)    //当数组数字总和不能被k整除时返回false.
    {
        cout << "False";
        return 0;
    }
    
    int target = sum / k;
    int used = 0;
    bool res = backtrack(k, 0, ivec, 0, used, target);
    if(res)
    cout << "True";
    else
    cout << "False";
    return 0;
}