Ep16 - Partition to K equal sum subsets | DSA | Codes available in description

[@NavyasriThalluri]

Thanksss a lot !! Keep doing tricky problems like this which are not famous and not avaliable on KZbin❤❤

[@arghya_0802]

This lecture was a real gem. Had a tough time solving the problem but now I really loved it. So my summary goes as such: 1. The problem states that we need to make exactly k subsets from the given array whose sum is same. So the reqSum of each subset is sumOfAllElements / k. 2. Now, we can solve this question using two ways. Either we can give the chance to each element whether to be included in bucket 1,2,3... k. In this way, we can have a solution whose time complexity will be O(k^N) which is very bad. Hence we think of further optimising our solution. 3. The second thought process can be- instead of asking each element whether they want to be filled in bucket number 1,2,3...till k we can fill them bucket wise. This is to say, we will first fill bucket 1, then we will move to bucket 2 and so on. Once our bucketCount == k +1 , it means we can make distribute the given array in k subsets, we will return true. 4. Another base condition will be, if bucketSum == reqSum, we will increment bucketCount by 1 and ask recursion to find remaining buckets whose sum is equal to reqSum but i should start from 0 and bucketSum should also start from 0. However, if bucketSum > reqSum, we don't need to move further, we can simply return false. 5. We also need a vector to keep track of all the elements we have picked for one particular bucket. We can call it by alreadypicked. 6. Now we just need to check whether one particular element is picked for one bucket or not. If yes, we try to find thr answer for i + 1 index 7. If not we have two choices. We will first pick the element by incrementing our sum and try to find the answer of i + 1 elements. 8. Else we will backtrack, decrement the sum and don't pick the i-th element at all and try to find for i+1 elements 9. At the end, we need to return OR of pick || don'tPick. 10. This code, however needs to be further optimised before getting submitted by using the memorization technique of DP. Time Complexity: O(2^N*K) { This is because we are filling all the buckets one by one and everytime one bucket is filled we start again from 0th index} Space Complexity: O(K*N) { We will keep on exploring all the possibilities until k buckets are not filled completely)

[@Anurag_Badwahe]

Bro i not understand first base condition .if(alreadyPicked[i]==1)return helper; This condition come from where ?can you please explain me

[@arghya_0802]

@@Anurag_Badwahe This means that if we have alreadyPicked i-th index, we definitely can't pick it in our next bucket, that's why we need to now check for (i+1)th index. This is to basically check whether we can include (i+1)th element or not

[@emtiazahmed5333]

Thank u❣️

[@bahanebaaz3232]

dude your summary always helps a lot for making notes😊😊

[@arghya_0802]

@@bahanebaaz3232 Thanks a lot bro. Glad it's helping a lot of people

[@webtechnology6439]

Yes, I Completed the recursion of all problems. In this lecture start dynamic programing.

[@Anurag_Badwahe]

You are doing great for us bhaiya.God bless you.

[@maazulhaque7293]

Episode - 16 Done Thanks fraz bhaiyya

[@AkshayKumar-qo2yn]

Notes: Pretty interesting problem, sort of like combination sum, where we check on each element if it should be in the current combination or not. The interesting part is the logic where we divide total sum by K and get target sum for each combination, and whenever we find a combination with target sum, put k = k - 1 and index = 0, and again call recursion. Which is why we get the provided time and space complexities T = O(2^kn) S = O(kn)

[@unknowncoder409]

1) If sum of total list is not divisible by k, then the k subsets of equal size cannot be formed. 2) There is still a possibility that the array cannot be divided into k subsets of equal sum even if sum of list is divisible by k. 3) We will traverse the array fully for all k subsets. 4) Each element at index can have choice either to go in the bucket or not. If we are considering the element at index i then we update the alreadyPicked vector to 1. 5) If alreadyPicked[i] == 1 then skip the current element and call the function recursively for rest of the elements. 6) if bucketSum > reqSum || index >= nums.size() then return false. 7) if bucketNum == k+1 then all the k buckets have been filled with required sum.

[@Shakib.Siddiqui]

Great faraz bhai i m consistent till now

[@mohdumar6990]

Way of teaching is very good and practical

[@BG-lj6fw]

great series! completing it to master recursion literally

[@sanketsatpathy3121]

Loved the way you teach. Trees ka bhi ek series nikalo jaldii!

[@anuraggulati2167]

Lecture lamba tha par maza aaya lecture 16 done 👌👌👌🙌🙌❤❤😍

[@unboxtheuniverse5336]

😂😂short lecture hi tha , DSA ka lecture isse lamba hota he

[@anuraggulati2167]

@@unboxtheuniverse5336 ok

[@DPCODE72]

Maja agya bhaiya ye lecture ko dekh kar!!

[@klvp_techie]

Logic: 1)if sum of list is not divisible by k then we can not construct k subsets from the list whose sum is equal 2)Even though the sum of list is divisible by k we may or may not get k subsets whose sum is equal 3)Subset sum is constructed by totalListSum // k for every element in the array which is not used have two choices either to go into the current bucket or not if it goes into the bucket mark the alreadyPicked array index as used and update the bucketSum, then ask the recursion to do for the remaining elements. if it does not goes to the bucket then ask the recursion to do for the next element if the bucketSum == reqSum then we have successfully constructed the current bucket so go fill the next bucket if bucketNum >= required subsets then return True as all the previous buckets are able to fill with reqSum if bucketSUM > reqSum or i >= len(array) return False Code: def isPossible(i,nums,k,bucketNum,bucketSum,reqBucketSum,alreadyPicked): if bucketNum > k: return True if bucketSum == reqBucketSum: return isPossible(0,nums,k,bucketNum + 1,0,reqBucketSum,alreadyPicked) if bucketSum > reqBucketSum: return False if i >= len(nums): return False if alreadyPicked[i] == 1: return isPossible(i+1,nums,k,bucketNum,bucketSum,reqBucketSum,alreadyPicked) else: # pick bucketSum += nums[i] alreadyPicked[i] = 1 op1 = isPossible(i+1,nums,k,bucketNum,bucketSum,reqBucketSum,alreadyPicked) bucketSum -= nums[i] alreadyPicked[i] = 0 # skip op2 = isPossible(i+1,nums,k,bucketNum,bucketSum,reqBucketSum,alreadyPicked) return op1 or op2 nums = [4,1,3,3,1,4,2,3,3,3] k = 3 totalListSum = sum(nums) if(totalListSum % k != 0): print(False) else: reqBucketSum = totalListSum // k alreadyPicked = [0] * len(nums) print(isPossible(0,nums,k,1,0,reqBucketSum,alreadyPicked))

[@unboxtheuniverse5336]

Thanks man

[@chiragkarnwal6740]

Thanks for the lecture sir everything understood and yeah curiously waitin for the dp as well!! ☺☺☺

[@nithins3895]

that was too tricky for me , but yeah understood, Thanks bhai

[@Abhishek-fo3fc]

Done understood ❤✅ on track, fully motivated, Thank you, Bhaiya #Fraz

[@aaravbagla4258]

dude i really love the way you explain keep it up thanks

[@hajikhalil4268]

what an explanation 🙌

[@amandixit8342]

Bhaiya shi mein ap Dil se chahte hai ki ap kuch value add kar pao ,shi woh dikh b raha hai apke efforts se ,apki baat karne se .

[@aryanbarnwal5645]

Thanks the code works perfectly.

[@it_08amanagarwal35]

Excellent Lecture bro good to be learning from u❤❤❤❤❤❤❤

[@sunilsarode152]

Thanks a lot , the tree you have drawn is not having the start of new bucket , sadly i am expecting lot from you ... please keep doing this good job 🙂

[@AdarshDalai]

Well going! Thank you for the lectures

[@KunalKumar-tm1zp]

lecture was superb. learnt a lot.

[@mdsufyankhan1029]

Tricky one but understood Nice explained ❣️

[@rajatsingh9537]

Can anyone help me with the dp optimisation i can see 4 changing parameters but my dp code giving wrong ans help me out if possible thanks

[@paragroy5359]

Thanks a lot for the videos. Great Content

[@TarunKumar-cn6in]

Awesome explanation 🙂

[@satyammishra6356]

Ep- 16 done bhaiya 😌

[@Ankitkr_47]

Thank you so much for the lectures

[@ratnasanjay]

Thankyou bhaiya for this nice session it was great

[@santoshkumarpaul5304]

Really u appreciate me ❤️ love u bhai 😘

[@deroxanime5273]

In this question we have to find whether the K subsets whose sum is equal (every subset has equal sum) is possible or not 1. The first intuitive thing we get is that we can totalsum of elements % K to see if it is totally divisible or not, if it is then it might be true and we will find the required sum in each bucket by totalsum/K otherwise it is obviously false. 2. If we consider an element to be put in each bucket then there will be a huge tree and it is not at all efficient. So we will consider each bucket one by one. Either we put this element in the bucket or skip that element. Once the bucketsum = requiredSum we will do a recursive call again by resetting the values and increasing the bucket number. 3. We will check if that element is already picked or not, if it is picked we will go ahead. Otherwise we will bucketsum += nums[i] and set alreadypicked[i] = 1 and declare a variable option1 in which we will move to the next element if we find the sum of the bucket equal to requiredSum by taking this element it will return true else false. Then we will undo our changes and pass another recursive call skipping this element to see it that fulfills our sum. We need either of those two options to be true which means we will have our sum either by taking this element or by skipping this element. We just need our sum, then we will return option1 || option2. What will be the base conditions?? I. Bucketsum == requiredsum return recursive call having resetted values with increment in bucketnumber II. Bucketsum > requiredsum return false III. i >= nums.size() return false IV. If alreadypicked == 1 V. Bucketnumber == k+1 return true Although this will give TLE as it needs DP solution for more efficiency but this is the correct solution its own way Time complexity: O(2^kn) where k is the number of buckets and n is the number of elements Space Complexity: O(kn)

[@someshkharat5849]

really loved this one... .one question, How do you or anyone can come up with this type of solution. i mean it looks easy after u code it but i would not have come up with this soln.

[@isikamaiti9116]

Ep-16 perfectly done ✅

[@jaikhatri4783]

I was able to think that recursive way it's just that I didn't think of already used

[@naturesrevolution]

in brute force how it gives 5 bucket at each level.. no. of bucket will reduce by one at each level right?

[@priyanshusingh8971]

completed and awesome experience...

[@AnilKumar-be3ip]

When are you planning to start dynamic programming Fraz ?

[@nilaanil1061]

Love your videos!

[@englishlnowledge486]

i donot understand the time complexity becaus (2^kn) signifies expansion on each level but in code when we find right bucket we narrow down to single path after ward we try to similar tree with even less number of available value in array. so time complexity should not be k*2^n?? Thank you you explantion is awesome!

[@pranavsharma7479]

not able to memoize and also the if base conditions are so much order dependent

[@dashundev1586]

Well ended this lecture

[@divyamkumar-oq5jz]

Please tell about the dp solution

[@emtiazahmed5333]

Lecture 16..._done bro🥰🥰

[@shivamsrivastava8093]

Pls provide the soln with Dynamic programming

[@jayantmishra6897]

whenever you code the second approch and after telling about the first approch as most of us are beginner we totally understand whatever you told us but we are not able to complete the solution. .So, please try to make recursion tree of the first approch it may increase the size of video but it would be helpful for us or you can create seperate video of that solution so we have two solution for a problem.

[@HarshRaj-kp7gk]

#op bhaiya 🥰🥰

[@xtremecase4247]

Thank u sir

[@asdsadafggggggg]

Bro love you thank you so much I am finding recursion easy just becuase of you... but please tell me one thing that how you plan to finish the syllabus before august by posting only 1 short video everyday..please don't take offence it is just a query to know your plan it would help us thanks

[@AnmolGupta-oj4lm]

Sir Please bring the Dp series. We are waiting

[@Gauravkumar-kc6xh]

Great

[@Truysジャ]

This solution gives tle in leetcode.

[@divyanshsagar]

Episode 16 done!

[@dashundev1586]

Maza aa gya

[@keshavraghav3896]

Getting TLE when doing the same in leetcode...

[@ksankethkumar7223]

I feel that time complexity should be O(k*2^n) because for every bucket you have some of the n elements to be selected and every element has 2 choices i.e. to be selected or not..So over all it will be 2^n for one bucket and k*2^n on the whole..please correct me if I am wrong fraz bhaiya..

[@samirpaul2]

Yes, Time Complexity is O(k * 2^n)

[@saqlain5275]

Assalam Alaikum FARAZ bhai! is there any video where you have implemented memoization. @LeadCodingbyFRAZ Can anyone guide me how to use dynamic programming techniques to actually submit this solution.

[@tejassankhla1264]

can anyone please tell how to decide changing parameters to be used in memoization or converting dp. having confusions and problem in converting this to dp

[@pritishpattnaik4674]

I guess ,as here 3 parameters are changing so, we can use a 3d vector to memoize it ?

[@KishankumarPatel]

Isaka last do line add karo bhai,,..!!!

[@yogesh3938]

mauli sir ne desperate kar diya

[@TanmayKhandelwal-z9v]

Just sort the array and while not picking the elements ..dont pick all those element which you don't chose to pick...

[@maitreyikshetrapal1644]

code showing tle error on leetcode

[@girikgarg8]

Bhaiya time complexity explain karna please 2^(nk) kaise hai?

[@brijeshkumarverma1223]

2:15

[@abhinavkumar7801]

I have written the same code with memoization but it is not passing all test cases. Can someone help me with this code by finding what is the error I am doing? class Solution { private: int helper(int i, int k, int bucketSum, int bucketNum, int reqSum, vector& nums, vector& picked, vector &dp) { if(bucketNum == k) { return true; } if(bucketSum == reqSum) { return dp[i][bucketSum][bucketNum] = helper(0, k, 0, bucketNum + 1, reqSum, nums, picked, dp); } if(bucketSum > reqSum) return false; if(i >= nums.size()) return false; if(dp[i][bucketSum][bucketNum] != -1) return dp[i][bucketSum][bucketNum]; if(picked[i] == 1) { return dp[i][bucketSum][bucketNum] = helper(i+1, k, bucketSum, bucketNum, reqSum, nums, picked, dp); } else { //Pick picked[i] = 1; bucketSum += nums[i]; bool pick = helper(i+1, k, bucketSum, bucketNum, reqSum, nums, picked, dp); picked[i] = 0; bucketSum -= nums[i]; //Not Pick bool notPick = helper(i+1, k, bucketSum, bucketNum, reqSum, nums, picked, dp); return dp[i][bucketSum][bucketNum] = pick | notPick; } } public: bool canPartitionKSubsets(vector& nums, int k) { int n = nums.size(); vector picked(n, 0); int sum = 0; for(int i = 0; i

[@abhishekc3556]

🔥🔥

[@madhurnarang2440]

Should TC not be O(K*(2^N)) ? Because one bucket at max takes O(2^N) time so other buckets would take almost the same time...... Guide me if I am wrong.

[@girikgarg8]

I also have same doubt

[@T_tintin]

I don't understand one thing. If we are unmarking all the elements after returning from the first bucket then will the recurssion not consider already used elements for the second bucket too? Becoz we have unmarked them then the same element may appear in both first and second bucket? If the array is like (4,3,2,1) and we need 2 equal subsets of sum 6 then will it be like (4,2) and (3,2,1). But here 2 is present in both bucket. Pls someone help me understand this 😅

[@tejassankhla1264]

we are marking visited as 0 when we have traversed with the elements visited including in the sum but unse bt nhi bani in other words no solution existed taking the element then we have returned and marked it as 0 and now will check kya ab hum solution tak pahuchte h kya

[@mridulsarma9022]

When will dp series come

[@ksankethkumar7223]

and also Can I know in general which is faster, an algorithm with complexity O(n^k) or an algorithm with O(k*2^n)??

[@SnapCodes]

depends on values of k and n

[@priyankakataria7922]

Can anyone give me the k^N time complexity solution?

[@Secret-tp6jl]

god🙏

[@ksankethkumar7223]

I was able to submit the code successfully when I sorted the input vector Here's My code: class Solution { public: bool canPartitionKSubsets(vector& nums, int k) { int sum =accumulate(nums.begin(),nums.end(),0); vectorvis(nums.size(),false); if(sum%k!=0) return false; int s=sum/k; sort(begin(nums),end(nums),greater()); // don't know the reason though! return is_possible(nums,0,s,k,0,vis); } bool is_possible(vector&nums,int curr,int sum,int k,int start,vector&vis) { if(k==1) return true; if(start>=nums.size()) //This line is important to avoid TLE return false; if(curr==sum) return is_possible(nums,0,sum,k-1,0,vis); for(int i=start;isum) continue; vis[i]=true; if(is_possible(nums,curr+nums[i],sum,k,i+1,vis)) return true; vis[i]=false; } return false; } };

[@mohdsaadalikhan7209]

why (i >= v.size()) is used? cant we simply use (i==v.size()); ??????????

[@vikashkumarbhagat3001]

Yes

[@ssd2898]

Lost interest because unable to validate my java code and provided java code here are not best quality.

[@bhuneshmeravi8411]

sir fatal error kyu aata hai code mei please reply🙏🙏🙏

[@ecs185_shaileshbharti3]

Reach++; ✌️💥

[@yashkamath9969]

Can anyone help me to write a code to print K subsets with equal sum.. Condition is that we can only a element once in a subset.. Input- 1 2 2 3 3 4 5 K=4

[@vicky-xf5nx]

🤧🤧9 videos delay 🙂

[@ashishdhal4614]

Looks like 3d dp problem problem

[@tusharjoshi1217]

Line 21 : return op1 | op2; Please somebody explain the working of | (Bitwise operator)

[@vikashkumarbhagat3001]

Used for binary operations

[@vikashkumarbhagat3001]

But here || is or

[@gauravsoni2919]

bool helper(int i,int nbucket,int bsum, int reqsum,int arr[], int n,vector&selected, int k){ if(i==n){ return false; } if(bsum>reqsum){ return false; } if(nbucket==k+1){ return true; } if(bsum==reqsum){ return helper(0,nbucket+1,0,reqsum, arr, n, selected,k); } if(selected[i]==0){ //pickup bsum+=arr[i] selected[i]=1; bool ans1=helper(i+1,nbucket,bsum,reqsum, arr,n, selected,k); //leave bsum-=arr[i]; selected[i]=0; bool ans2=helper(i+1,nbucket,bsum,reqsum, arr, n , selected,k); return ans1||ans2; } }else{ return helper(i+1,nbucket,bsum,reqsum,arr,n,selected,k); } } bool isKPartitionPossible(int arr[], int n, int k) { //Your code here int sum=0; for(int i=0;i

[@sunnyvlogs__]

Anyone getting wrong answer for this ques. on Leetcode?

[@vikashkumarbhagat3001]

Tle

[@vikaskotwani9573]

I am here to defect the domino effect.

[@mohammedsaqib1250]

Samj nai aaya 😥

[@LearnYardYT]

Fir se repeat krlo

[@rahul-cp2td]

I lost my motivation because I can't understand better because of the my English problem...

[@LearnYardYT]

Then how will you speak in English during interviews

[@vuthunoorilahari2380]

Hey...I can help you