题解 | 划分等和序列

class Solution {
public:
    vector<int> used;  //记忆数组，记录已经使用过的元素；
    bool candivide(vector<int>& nums, int k) {
        used.resize(nums.size(), 0);  //0表示没有被使用过

        int all = 0;
        for(int i:nums)all += i;
        if( all % k ) return false;  //每组目标不是整数false；
        int target = all / k;   

        //方便进行剪枝，大的在前，递归次数少（先满足），同时递归时跳过相同的不能采用的元素；
        sort(nums.rbegin(), nums.rend());  
        if(nums[0] > target)return false; //一个元素大于target，false

        return solution(nums, 0, 0, k, target);
    }

    bool solution(vector<int>& nums, int start, int cur_sum, int k, int target){
        if(k == 0) return true;   //最终目的
        if(cur_sum == target) return solution(nums, 0, 0, k-1, target);

        for(int i = 0; i<nums.size(); ++i){
            if(used[i] || cur_sum + nums[i] > target)
                continue;

            used[i] = 1;
            if(solution(nums, i, cur_sum+nums[i], k, target))return true;  //采用
            used[i] = 0;   //退回

            while(i+1<nums.size() && nums[i] == nums[i+1])i++;  //剪枝
        }

        return false;
    }
};