Advertisement
imashutosh51

Partition to K Equal Sum Subsets

Jul 23rd, 2022 (edited)
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. //TC. O(2^(N*K)) because we are either selecting or not selecting to 2^n elements because we come back to 0 after every //group with required sum
  2. //space complexity : O(N)
  3.     bool solve(int i,vector<int>&nums,int k,int sum,int req_sum,vector<bool>&vis){
  4.         if(k == 1) return true;     //we are not checking for the last subset because sum is divisible by k and if k-1 subset is found so ofocurse kth
  5.         if(i == nums.size()) return false;  //will also be present,same region for i==nums.size() return false;
  6.         if(sum == req_sum) return solve(0,nums,k-1,0,req_sum,vis);
  7.        
  8.         bool op1 = false;
  9.        
  10.         if(!vis[i] and sum + nums[i] <= req_sum){
  11.             vis[i] = true;
  12.             if(solve(i+1,nums,k,sum + nums[i],req_sum,vis)) return true;
  13.             vis[i] = false;
  14.         }
  15.        
  16.         return solve(i+1,nums,k,sum,req_sum,vis);            
  17.     }
  18. class Solution {
  19. public:
  20.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  21.         int n = nums.size();
  22.         int sum = accumulate(nums.begin(),nums.end(),0);
  23.         if(n < k or sum % k != 0) return false;
  24.         int req_sum = sum/k;
  25.         // sort(nums.begin(),nums.end(),greater<int>());
  26.         vector<bool> vis(nums.size());
  27.         return solve(0,nums,k,0,req_sum,vis);
  28.     }
  29.    
  30. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement