C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-05-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return bool布尔型
     */
    bool candivide(vector<int>& nums, int k) {
        
        int sum = 0;
        for(auto& i : nums){
            sum += i;
        }
        
        if(sum % k != 0){
            return false;
        }
        
        sort(nums.rbegin(), nums.rend());
        
        int target = sum / k;
        auto arr = vector<int>(k);
        
        //auto visited = vector<bool>(nums.size());
        return dfs(nums, target, 0, arr);
        
    }
    
    bool dfs(vector<int>& nums, int target, int index, vector<int>& arr){
        if(index == nums.size()){
            return true;
        }
        
        for(auto& i : arr){
            if(i + nums[index] > target){
                continue;
            }
            i += nums[index];
            if(dfs(nums, target, index + 1, arr)){
                return true;
            }
            i -= nums[index];
        }
        
        return false;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-06-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return bool布尔型
     */
    #include <vector>
    bool candivide(vector<int>& nums, int k) {
        // write code here    
        int sum=0;
        for(auto& n:nums) sum+=n;
        if(sum%k!=0) return false;
        sort(nums.rbegin(),nums.rend());
        int target=sum/k;
        vector<int> buckets(k,target);
        return dfs(nums,buckets,0);
    }
    
    bool dfs(vector<int>& nums,vector<int>& buckets,int index){
        if(index>=nums.size()) return true;
        for(int i=0;i<buckets.size();i++){
            if(nums[index]>buckets[i]) continue;
            if(i>0&&buckets[i]==buckets[i-1]) continue;
            buckets[i]-=nums[index];
            if(dfs(nums,buckets,index+1)) return true;
            buckets[i]+=nums[index];
        }
        return false;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-05-19

class Solution {
public:
    bool candivide(vector<int>& nums, int k) {
        if (k > nums.size()) return false;
        int sum = 0;
        for (int val : nums) sum += val;
        if (sum % k != 0) return false;

        int target = sum / k;
        vector<int> bucket(k);
        sort(nums.begin(), nums.end(), greater<>());
        return backtrack(nums, 0, bucket, target);
    }

private:
    bool backtrack(const vector<int>& nums, int idx,
                   vector<int>& bucket, int target) {
        if (idx == nums.size()) return true;

        for (int i = 0; i < bucket.size(); i++) {
            if (bucket[i] + nums[idx] > target) continue;
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;

            bucket[i] += nums[idx];
            if (backtrack(nums, idx + 1, bucket, target))
                return true;
            bucket[i] -= nums[idx];
        }

        return false;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return bool布尔型
     */
    bool candivide(vector<int>& nums, int k) {
        // write code here
        int sum=0;
        for(auto &i:nums)
        {
            sum+=i;
        }
        if(sum%k!=0)
        {
            return false;
        }
        sort(nums.rbegin(),nums.rend());
        int target=sum/k;
        auto arr=vector<int>(k);
        return dfs(nums,target,0,arr);
    }
    bool dfs(vector<int> &nums,int target,int index,vector<int> &arr)
    {
        if(index==nums.size())
        {
            return true;
        }
        for(auto &i:arr)
        {
            if(i+nums[index]>target)
            {
                continue;
            }
            i+=nums[index];
            if(dfs(nums,target,index+1,arr))
            {
                return true;
            }
            i-=nums[index];
        }
        return false;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-07-28

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return bool布尔型
     */
    vector<bool> state;
    bool flag = false;
    bool candivide(vector<int>& nums, int k) {
        int n = nums.size();
        state = vector<bool>(n, false);
        int sum = 0;
        for(auto i:nums) sum += i;
        if(sum % k) return false;
        int avg = sum / k;
        cout << sum << " " << avg << endl;
        sort(nums.begin(), nums.end());
        return dfs(nums, k, avg);
        //return flag;
    }
    bool dfs(vector<int>& nums, int k, int target){
        if(flag) return true;
        if(k == 0){
            //flag = true;
            return true;
        }
        if(target == 0){
            return dfs(nums, k-1, target );
        }
        //if(target < 0) return ;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > target || state[i]) continue;
            state[i] = true;
            if(dfs(nums, k, target - nums[i])) return true;
            state[i]  = false;
        }
        return false;
    }
};