Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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
- //space complexity : O(N)
- bool solve(int i,vector<int>&nums,int k,int sum,int req_sum,vector<bool>&vis){
- 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
- if(i == nums.size()) return false; //will also be present,same region for i==nums.size() return false;
- if(sum == req_sum) return solve(0,nums,k-1,0,req_sum,vis);
- bool op1 = false;
- if(!vis[i] and sum + nums[i] <= req_sum){
- vis[i] = true;
- if(solve(i+1,nums,k,sum + nums[i],req_sum,vis)) return true;
- vis[i] = false;
- }
- return solve(i+1,nums,k,sum,req_sum,vis);
- }
- class Solution {
- public:
- bool canPartitionKSubsets(vector<int>& nums, int k) {
- int n = nums.size();
- int sum = accumulate(nums.begin(),nums.end(),0);
- if(n < k or sum % k != 0) return false;
- int req_sum = sum/k;
- // sort(nums.begin(),nums.end(),greater<int>());
- vector<bool> vis(nums.size());
- return solve(0,nums,k,0,req_sum,vis);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement