C++ Solution (3ms)


  • 0
    S
    class Solution {
    public:
        bool find(vector<int>nums, int start, int n, int cursum, int target, int k, vector<bool>&taken){
            if(k == 1)
                return true;
            else if(cursum == target)
            {
                return find(nums, 0, n, 0, target, k-1, taken);
            }
            for(int i = start; i < n; i++)
            {
                if(taken[i])
                    continue;
                if(cursum + nums[i] <= target){
                    taken[i] = true;
                    if(find(nums, i+1, n, cursum + nums[i], target, k, taken))
                        return true;
                    taken[i] = false;
                }
             }
            return false;
        }
        bool canPartitionKSubsets(vector<int>& nums, int k) {
           int n = nums.size();
            if(k == 1)
                return true;
            if( k > n)
                return false;
            int sum = 0;
            for(auto i : nums)
                sum += i;
            if(sum % k != 0)
                return false;
            sort(nums.begin(), nums.end());
            reverse(nums.begin(), nums.end());
            // sum of each subset = sum/k
            vector<bool>taken(n, false);
            int target = sum/k;
            return find(nums, 0, n, 0, target, k, taken);
        }
    };
    

Log in to reply
 

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