C++ solution use backtrace


  • 1
    C
    class Solution {
    public:
        bool fun(vector<int>& nums, int idx, int sum){
            if( sum == 0 ){
                return true;
            }
            for( int i = 0; i<nums.size(); i++){
                if( nums[i] == 0 )
                    continue;
                if( sum - nums[i]>=0 ){
                    int tmp = nums[i];
                    nums[i] = 0;
                    if( fun(nums, i, sum-tmp ) ){
                        return true;
                    }
                    nums[i] = tmp;
                }else{
                    return false;
                }
            }
            return false;   
        }
        bool canPartitionKSubsets(vector<int>& nums, int k) {
            
            int sum = 0;
            sort(nums.begin(), nums.end());
            reverse(nums.begin(), nums.end());
            for( int i = 0; i<nums.size(); i++){
                sum += nums[i];
            }
            sum /= k;
            for(int  i= 0; i<k; i++){
                if(!fun(nums, 0, sum)){
                    return false;
                }
            }
            return true;
        }
    };
    

  • 0
    Y
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.