698. Partition to K Equal Sum Subsets

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int N = nums.size();
        int sm = 0;
        for(int n : nums) sm+=n;
        if(sm%k != 0) return false;
        int ave = sm/k;
        vector<bool> used(N, false);
        sort(nums.begin(), nums.end(), greater<int>());
        if(nums[0]>ave) return false;
        return bt(nums, used, ave, ave, k);
    }
    bool bt(vector<int>&nums, vector<bool>& used, int s, const int ave, int p) {
        if(s< 0) return false;
        if(p< 0) return false;
        if(p==0) return true;
        if(s==0) return bt(nums, used, ave, ave, p-1);
        for(int i=0; i<nums.size(); i++) {
            if(!used[i]) {
                //if(nums[i]>ave) return false;
                used[i] = true;
                bool b = bt(nums, used, s-nums[i], ave, p);
                if(b) return true;
                used[i] = false;
            }
        }
        return false;
    }