The time complexity of the recursive solution is also 2^N x N. We know that we will get 2^N subset sums and at last we sort the array so 2^N + (2^N)log(2^N) ~= 2^N x N
For simple variables (non-container types like int, float, etc.)(here it is sum), we don't need to adjust them explicitly after including them in a recursive call. The reason is each recursive call creates its own local variables, and any modifications we make within a recursive call are isolated and do not affect other recursive calls.
If we sort the array before passing in function func, then no need to sort sumSubset array by doing this, We have also reduced the time complexity from O ( 2^n + (2^n) log(2^n)) to O (2^n + n Log(n)).
The way you makes us understand each and every concept is just incredible bhaiya.For those finding it tough or not confident enough in recursion,i would suggest to solve more questions on trees.
If you just reverse the order of recursive calls (don't pick first and pick second), you would automatically get the resultant subset sum array in sorted form. This way one can avoid the final sorting of the result.
@@26.aniketmatkar20 bruh,,, it literally passed,,, and its sorted... idk how its getting sorted tho.. gotta draw recursive tree... however they never asked for sorted output tho ArrayList subsetSums(ArrayList arr, int N){ // code here ArrayList sol = new ArrayList(); setsum(sol,arr,N,0,0); return sol; } void setsum(ArrayList sol, ArrayList arr, int N, int i, int sum){ if(i==N){ sol.add(sum); return; } // 1.skip ele and proceed setsum(sol,arr,N,i+1,sum); // 2.pick ele, add sum and proceed setsum(sol,arr,N,i+1,sum+arr.get(i)); }
Couldn't Thank you enough Raj bhaiyya, I am currently going through Recursion playlist of yours, and I could absolutley say ,no one could have taught us better than this. Thank u soo much for your work.
I was able to grasp this as it's a kind of Subsequence but we are only concerned with its Sum..... To think i was able to think of a logic myself.... Wowww all thanx to you 🙏♥️🤩🔥
Actually we dont need to sort because if you first call for not pick then pick we get subset sum in ascending order thus T.C= O(2^N) . Code that is submited without sorting : void fun(int index, int sum , vector &arr,int N,vector &ans) { if(index==N) { ans.push_back(sum); return; } fun(index+1,sum,arr,N,ans); fun(index+1,sum+arr[index],arr,N,ans); } vector subsetSums(vector arr, int N) { vector ans; fun(0,0,arr,N,ans); return ans; }
@take U forward Thanks for the amazing recursion and dynamic programming series, For this question I think we can have TC = 2^N by sorting the given array first and deciding to not pick before picking. That way the resultant array will be in sorted order!
@@mridulshroff824 Because we need to reach to the lower sums before reaching to higher sum values.For example, take [ 2, 5, 1] as the arr.We sort it to [ 1, 2, 5] why? bcz, we will go and find all possible subsets starting with 1 ,then with 2 then only 5 - thus they will be in ascending order.Now, lets say you have slected [1,2] and the recursion call is suppose to pick/not pick the element 5 , by not picking it, my sum is 1+2=3 but by picking its 1+2+5=8 . so, which call i should make to get the least sum first(ascending order) ? Its the not pick case right ...
solved this under a minute, really quality content , best way to give back your learnings, true guru !!! . Eagerly waiting to meet you one day and I surely will ..
We just need to sort the initial array(n logn) , and do not pick and then pick. So we end up getting an array of sums in sorting order(2^n for generating) T.c = O(n logn + 2^n) = O(2^n) S.c = O(2^n)
we can reduce the time for sorting by modifying the code as below - void solve(vector arr,int i,vector &ans,int sum){ if(i == arr.size()){ ans.push_back(sum); return; } solve(arr,i+1,ans,sum); sum = sum + arr[i]; solve(arr,i+1,ans,sum); } vector subsetSums(vector arr, int N) { vector ans; solve(arr,0,ans,0); return ans; }
Just a doubt in the code: When you are doing sum + arr[i], that means you are picking that element right. When you do to not pick recursion, dont you have to do sum = sum - arr[i] and then call recursion.
instead of sorting the array with subsets sum, we can just sort the array which contains n elements. and then we have to first call the function in which we do not include current element in the sum. this will result in sorted result only. and also sorting time would be reduced
We can sort the input array and then do recursion such a way that we take smallest elements first. This will generate subset sum smallest to largest and we don't need to sort the final array at the end.
@@your_name96 no we don't need to sort the final array which has the size of 2^n. We sort the input array which has size n. So time complexity will be less.
Thanks a lot for adding the visualization of the RECURSIVE CALL, it really helps in getting the proper understanding. Thanks a lot for your effort and hardwrork. Really Helpful.After watching this i am going to be member of your chanel.Really well explained.
Thank you so much Bhaiya...I am starting to get a better idea of recursive calls know and I am say this with a 100% certainity that your videos have a major role in all this ❤
So basically how we can differentiate between subsequence and subset, subsequence can be like which follows order of array, but then too need some more points
I have a doubt that when do we make the helper function return something and when do we not return anything, would it be possible if in this solution the 'func' functions return the final arraylist?
The below code avoids sorting and has O(2^n) time complexity instead of O(2^n)+O(2^n log(2^n)) void comb(vector &sums, vector &arr, int i, int n, int sum){ if(i>=n){ sums.emplace_back(sum); return; } comb(sums,arr,i+1,n,sum); comb(sums,arr,i+1,n,sum+arr[i]); } vector subsetSums(vector arr, int N) { // Write Your Code here vector sums; comb(sums,arr,0,N,0); return sums; }
Because of the earlier videos and ruminating in my sleep, I could solve this, honestly I did one mistake that is keeping a vector storing the subset, should have saved a sum variable.
we can remove the time complexity of sorting the solution by making the right sub-tree to the left and the left sub-tree to the right. Please try it once, this means swapping the recursive function calls.
looking at these combination problam at saying abhi to ye sb bhaiya ye padhaya subsequences me tha and then i tried myself and got ac , best feeling ever
I have done using this method. Does this have any down side? There is no requirement of sorting here vector subsetSums(vector arr, int N) { if(N == 0) { vector ans; ans.push_back(0); return ans; } vector output = subsetSums(arr,N-1); int size = output.size(); for(int i=0;i
📢🔥🔥What is the space complexity?????? Is it O(N) cuz at max there would be N revursive call waiting in the stack. (there are n+1 levels in the stack space tree). Plz clarify
if we call the function that does not include first element in current sum and then call second function. then we will get subset sum in sorted order than there is not need to sort. public void ss(ArrayList arr, int n,int sum,ArrayList sub){ // code here if(n==arr.size()) { sub.add(sum); return ; } ss(arr,n+1,sum,sub); ss(arr,n+1,sum+arr.get(n),sub); }
I think It can be done in single recursive call. vector subset(vector &num,int i) { // Write your code here. vector ans; if(i==num.size()){ ans.push_back(0); return ans; } ans = subset(num,i+1); int size=ans.size(); for(int j=0;j
understood sir, but why we are sorting it again in the main function? i saw this in the documentation of this problem int main() { vector < int > arr{3,1,2}; Solution ob; vector < int > ans = ob.subsetSums(arr, arr.size()); sort(ans.begin(), ans.end()); cout
//sum of subsets in sorted order //t.c is for every index i have two choice pick and not pick for example i have 3 indxes the i will //have total 6 choices p/np for each indexs hence for n indexes i will have 2^n choicess //also there is extra 2^n*log(2^n) t.c for sorting the ans array hence total t.c is (2^n * 2^n *log(2^n)) class Solution { public: void solve(vector &a, int index,int s,int N,vector &ans) {
if(index==N) { ans.push_back(s); return; } //picking element from the index solve(a,index+1,s+a[index],N,ans); // s=s-a[index];aisa kuch nhi hoga s datastructure nhi hai //s ek simple variable hai samjha kuch nhi krna hai //decreasing the sum //simple backtrack //pick notpick ka function easily call ho jayega samjha be solve(a,index+1,s,N,ans);
} public: vector subsetSums(vector a, int N) { vectorans; int index=0; int s=0; solve(a,index,s,N,ans); sort(ans.begin(),ans.end() ); return ans; } };
Sort array in reverse order and do not take first and next call for take this way we get sum in inc order automatically..I am assuming all elts to be distinct..tc 2^n and SC is 2^n
Hey Striver, Big fan and thank you for the amazing series, but in this question, we are asked about subsets and what you have explained is the solution for subsequences. In your video on subsequences, you had explained the difference between subsets and subsequences - "Subsequences can be contiguous as well as non-contiguous but subsets are always contiguous". This point can also be observed if we go to the problem link and see the examples mentioned.
I do think so that the time complexity of this approach would be O(2^nlog(2^n)) = O(n* 2^n). Please have a look at my code below, it is accepted on gfg and I think it is having time complexity O(2^n) only, please correct me I am wrong. The idea is still similar to either pick an element or not pick the element but we are only pushing sum+arr[n-1] value into the vector. Also, the recursive function will not consider of the case when no element is picked hence we have to push_back(0) into the vector at the very beginning. void subSum(vector &arr, int n, int sum, vector &s) { if(n == 0) { return; } s.push_back(sum+arr[n-1]); subSum(arr, n-1, sum, s); subSum(arr, n-1, sum+arr[n-1], s); } vector subsetSums(vector arr, int N) { vector s; s.push_back(0); subSum(arr, N, 0, s); return s; }
We pass sum+arr[i] to next function call when picking the current element and do not change the value of sum itself, so when going for not picking recursive call we just pass sum.
I guess Time Complexity can be reduced significantly!! Instead of sorting the result array of size of size 2^n we can sort the input array of size of size n. And while picking instead of pick, FIRST perform NOT pick THEN pick class Solution{ ArrayList subsetSums(ArrayList arr, int N){ Collections.sort(arr); ArrayList result = new ArrayList(); subsetSums(0, 0, arr, result); return result; } void subsetSums(int i, int currSum, ArrayList arr, ArrayList result) { if(i == arr.size()) { result.add(currSum); return; } //not pick ith element for sum subsetSums(i+1, currSum, arr, result); //pick ith element for sum subsetSums(i+1, currSum+arr.get(i), arr, result); } }
@@nileshchandra6435 can u please elaborate your point, as the code above passes all the test cases on GFG including [1,2,3] (as first I am performing NOT pick then PICK)
Just one confirmation i need incase of list we remove last element and incase of variable we just return it. It happens because of pass by value and pass by reference?
Here is the Java Code for Reference ArrayList subsetSums(ArrayList arr, int N){ ArrayListl=new ArrayList(); backtrack(l,arr,N,0,0); return l; } public static void backtrack(ArrayListl,ArrayListarr,int n ,int i,int sum){ if(i==n){ l.add(sum); return; } backtrack(l,arr,n,i+1,sum); backtrack(l,arr,n,i+1,sum+arr.get(i)); }
May be I am not able to understand the logic properly but to the extent that I understand I had one doubt when we don't pick any index then our sum is 0, and when we move to left of that than also our sum will be 0 so what I am trying to say is that we should be having duplicate values, can some one help me and let me know, if I am missing something
so, in subsequence for picking, we are removing one element (last element) and then we go for not picking, but here we are not removing because sub-set means a continuous array. is this the correct reason? can anyone tell?
C++ Code: github.com/striver79/SDESheet/blob/main/SubsetSumsC%2B%2B
Java Code: github.com/striver79/SDESheet/blob/main/SubsetSumsJava
Instagram: instagram.com/striver_79/
Where's the link for the power set?
can you please make a video on power set as you said?
czcams.com/video/b7AYbpM5YrE/video.html the link for powerset
@@aasthachauhan4385 it is there
@@aasthachauhan4385 Power set is very easy...spend some time on it and you yourself can develop an algorithm for it
You have a lot of patience to trace out the whole recursion tree.. thanks a lot for this :)
what else do you expect from a 6star coder,these nothing for him xD
humility is very rare these days though@@debjitdutta17
The first recursion sum I solved on my own and got accepted in the first go....thank u so much !!
Same goes with me. Hehhehe
Same Broooooooooo !
same!!
The time complexity of the recursive solution is also 2^N x N. We know that we will get 2^N subset sums and at last we sort the array so 2^N + (2^N)log(2^N) ~= 2^N x N
For simple variables (non-container types like int, float, etc.)(here it is sum), we don't need to adjust them explicitly after including them in a recursive call. The reason is each recursive call creates its own local variables, and any modifications we make within a recursive call are isolated and do not affect other recursive calls.
If we sort the array before passing in function func, then no need to sort sumSubset array
by doing this, We have also reduced the time complexity from O ( 2^n + (2^n) log(2^n)) to O (2^n + n Log(n)).
Yeah..but for that we we need to call right subtree before calling left subtree.
@@venkateshn9884 we need to sort in decreasing order in that case rit?
@@rakshankotian2737 Exactly 💯
You can't always do that , there could be chances , for certain test cases where the sorting order might go out of order
Example [6,4,3,2]
@@user-le6ts6ci7h Nooo ....it will also work ,if you sort at starting ,we can achieve using O (2^n + n Log(n)),no issue on this
The way you makes us understand each and every concept is just incredible bhaiya.For those finding it tough or not confident enough in recursion,i would suggest to solve more questions on trees.
If you just reverse the order of recursive calls (don't pick first and pick second), you would automatically get the resultant subset sum array in sorted form. This way one can avoid the final sorting of the result.
Woahh...That's a good observation though. Thanks shivam!
No it will not work, it will just reverse the answer vector. One element i.e 4 will remain unsorted
No it'll only reverse the output, it won't be sorted.
@@26.aniketmatkar20 bruh,,, it literally passed,,, and its sorted... idk how its getting sorted tho.. gotta draw recursive tree... however they never asked for sorted output tho
ArrayList subsetSums(ArrayList arr, int N){
// code here
ArrayList sol = new ArrayList();
setsum(sol,arr,N,0,0);
return sol;
}
void setsum(ArrayList sol, ArrayList arr, int N, int i, int sum){
if(i==N){
sol.add(sum);
return;
}
// 1.skip ele and proceed
setsum(sol,arr,N,i+1,sum);
// 2.pick ele, add sum and proceed
setsum(sol,arr,N,i+1,sum+arr.get(i));
}
The thing is we dont need to SORT, they're sorting it in the DRIVER code
The first recursive approach which I understood clearly.. Thank you so much sir.
Couldn't Thank you enough Raj bhaiyya, I am currently going through Recursion playlist of yours, and I could absolutley say ,no one could have taught us better than this.
Thank u soo much for your work.
I was able to grasp this as it's a kind of Subsequence but we are only concerned with its Sum..... To think i was able to think of a logic myself.... Wowww all thanx to you 🙏♥️🤩🔥
Actually we dont need to sort because if you first call for not pick then pick we get subset sum in ascending order thus T.C= O(2^N) . Code that is submited without sorting :
void fun(int index, int sum , vector &arr,int N,vector &ans)
{
if(index==N)
{
ans.push_back(sum);
return;
}
fun(index+1,sum,arr,N,ans);
fun(index+1,sum+arr[index],arr,N,ans);
}
vector subsetSums(vector arr, int N)
{
vector ans;
fun(0,0,arr,N,ans);
return ans;
}
Hey , can you explain why we are not subtracting arr[i] from sum when backtracking in case of not take.
@22.37
@@tanyagupta1176 beacuse we dont add it we just skip that index in parameter
@take U forward
Thanks for the amazing recursion and dynamic programming series,
For this question I think we can have TC = 2^N by sorting the given array first and deciding to not pick before picking. That way the resultant array will be in sorted order!
Can you explain how not picking before picking reduces TC? I couldn't understand.
@@mridulshroff824 Because we need to reach to the lower sums before reaching to higher sum values.For example, take [ 2, 5, 1] as the arr.We sort it to [ 1, 2, 5] why? bcz, we will go and find all possible subsets starting with 1 ,then with 2 then only 5 - thus they will be in ascending order.Now, lets say you have slected [1,2] and the recursion call is suppose to pick/not pick the element 5 , by not picking it, my sum is 1+2=3 but by picking its 1+2+5=8 . so, which call i should make to get the least sum first(ascending order) ? Its the not pick case right ...
I think if we select not picking first, then in the Array (1,2,3)
3 would be picked up first...
@@mridulshroff824 Because then we don't need to sort the output array in the end.
I have made this question from myself using both iterative and recursive approach thanks striver from bottom of my heart ❤
Moving to L11 , this was an easy one 👍
solved this under a minute, really quality content , best way to give back your learnings, true guru !!! . Eagerly waiting to meet you one day and I surely will ..
We just need to sort the initial array(n logn) , and do not pick and then pick. So we end up getting an array of sums in sorting order(2^n for generating)
T.c = O(n logn + 2^n) = O(2^n)
S.c = O(2^n)
it wont't work
we can reduce the time for sorting by modifying the code as below -
void solve(vector arr,int i,vector &ans,int sum){
if(i == arr.size()){
ans.push_back(sum);
return;
}
solve(arr,i+1,ans,sum);
sum = sum + arr[i];
solve(arr,i+1,ans,sum);
}
vector subsetSums(vector arr, int N)
{
vector ans;
solve(arr,0,ans,0);
return ans;
}
Just a doubt in the code: When you are doing sum + arr[i], that means you are picking that element right. When you do to not pick recursion, dont you have to do sum = sum - arr[i] and then call recursion.
instead of sorting the array with subsets sum, we can just sort the array which contains n elements. and then we have to first call the function in which we do not include current element in the sum. this will result in sorted result only. and also sorting time would be reduced
Same this will reduce the TC from 2n log 2n to n log n
he is a legend for the first time I have solved a recursion question myself
First Viewer, just wanted to say, You're doing amazing job! Keep up the good work!
congratulations bhaiya apka google me hogya na!, Main bhi aa rha hu jldi hi milte hai
Thnaks striver, did all that by myself by just seeing half the approach.
We can sort the input array and then do recursion such a way that we take smallest elements first. This will generate subset sum smallest to largest and we don't need to sort the final array at the end.
umm, so you are adding code/logic complexity with no improvement in time complexity ?
@@your_name96 no we don't need to sort the final array which has the size of 2^n. We sort the input array which has size n.
So time complexity will be less.
@@ganapatibiswas5858 oh yes,will try to implement this one
ye qsn sbse easy tha phle k 2-3 lectures me qsns ko 2-3 bar rewind krke dekhna pdh rha tha lekin isme niii thnx😃
Thanks a lot for adding the visualization of the RECURSIVE CALL, it really helps in getting the proper understanding. Thanks a lot for your effort and hardwrork. Really Helpful.After watching this i am going to be member of your chanel.Really well explained.
Thank you so much Bhaiya...I am starting to get a better idea of recursive calls know and I am say this with a 100% certainity that your videos have a major role in all this ❤
Understood bro i just understood the method without pseudo code and wrote program myself. Great explanation
Bhaiya mtlb kaise btaun apne to kamal kardia
ye question mne khud try kia aur first attempt m kardia
Apse padhkar maza agya.
STRIVERR!!
I watched the first couple of minutes of your video and then was able to code the solution alone!!! Thank you for the amazing content!!!!!!
If someone does this tracing for merge sort till the end his confidence increases a lot in recursion
Best explanation i have found here in this video thanks a lot for ur hard work nd keep doing
BHAIYYA PLEASE EK REQUEST HAI EK VIDEO ISPE BHI BANAO DEPTH ME KI HUM POP BACK KAB KARTE HAI BACKTRACK KE TIME USME BOHOT CONFUSION HO RAHA HAI
You said TC of recursive solution is 2^N + 2^N log (2^N), isn't it equal to 2^N + N*2^n(log 2) = N*2^N + 2^N = O(N * 2^N) same as iterative one?
yes you're right.
thank you bhaiya, for your awesome informative videos of most important DSA question, aap jldi thik ho jao ......
I really afraid of this questions but when I see your video some magic happen
So basically how we can differentiate between subsequence and subset, subsequence can be like which follows order of array, but then too need some more points
why sum is not minus when we came back and go to not pick option?
I have a doubt that when do we make the helper function return something and when do we not return anything, would it be possible if in this solution the 'func' functions return the final arraylist?
UNDERSTOOD... !!!
Thanks striver for the video... :)
one of the best explanation!!!!!!!!
The below code avoids sorting and has O(2^n) time complexity instead of O(2^n)+O(2^n log(2^n))
void comb(vector &sums, vector &arr, int i, int n, int sum){
if(i>=n){
sums.emplace_back(sum);
return;
}
comb(sums,arr,i+1,n,sum);
comb(sums,arr,i+1,n,sum+arr[i]);
}
vector subsetSums(vector arr, int N)
{
// Write Your Code here
vector sums;
comb(sums,arr,0,N,0);
return sums;
}
Because of the earlier videos and ruminating in my sleep, I could solve this, honestly I did one mistake that is keeping a vector storing the subset, should have saved a sum variable.
we can remove the time complexity of sorting the solution by making the right sub-tree to the left and the left sub-tree to the right. Please try it once, this means swapping the recursive function calls.
thnks bhaiya i was able to do combination sum 3 on my own only because of u
instead of storing it in arraylist we can use treeset to reduce the extra overhead of sorting the list
TreeSet would still take logN time to insert each sum. So for n subsets sum it'll take n*logn time, which is same as sorting the final container.
solved in 8 min just by reading problem statement ❤🔥❤🔥❤🔥
looking at these combination problam at saying abhi to ye sb bhaiya ye padhaya subsequences me tha and then i tried myself and got ac , best feeling ever
I have done using this method. Does this have any down side? There is no requirement of sorting here
vector subsetSums(vector arr, int N)
{
if(N == 0)
{
vector ans;
ans.push_back(0);
return ans;
}
vector output = subsetSums(arr,N-1);
int size = output.size();
for(int i=0;i
📢🔥🔥What is the space complexity??????
Is it O(N) cuz at max there would be N revursive call waiting in the stack. (there are n+1 levels in the stack space tree).
Plz clarify
The space complexity here will be of O(N) because that will be the depth of the recurs ion tree.
Thank you for using real english. I subscribe your soul 👍
if we call the function that does not include first element in current sum and then call second function. then we will get subset sum in sorted order than there is not need to sort. public void ss(ArrayList arr, int n,int sum,ArrayList sub){
// code here
if(n==arr.size())
{
sub.add(sum);
return ;
}
ss(arr,n+1,sum,sub);
ss(arr,n+1,sum+arr.get(n),sub);
}
he is the definition of handsome with brains!!
I think It can be done in single recursive call.
vector subset(vector &num,int i)
{
// Write your code here.
vector ans;
if(i==num.size()){
ans.push_back(0);
return ans;
}
ans = subset(num,i+1);
int size=ans.size();
for(int j=0;j
understood sir, but why we are sorting it again in the main function? i saw this in the documentation of this problem
int main() {
vector < int > arr{3,1,2};
Solution ob;
vector < int > ans = ob.subsetSums(arr, arr.size());
sort(ans.begin(), ans.end());
cout
Can anybody tell.. why we r not doing sum-arr[i] when we r returning... so the previous sum dont add... as we do in other subset problem
we are passing sum+arr[i] directly so when recursion return and goes to not take f(ind,sum) sum is passed not sum+arr[ind]
//sum of subsets in sorted order
//t.c is for every index i have two choice pick and not pick for example i have 3 indxes the i will
//have total 6 choices p/np for each indexs hence for n indexes i will have 2^n choicess
//also there is extra 2^n*log(2^n) t.c for sorting the ans array hence total t.c is (2^n * 2^n *log(2^n))
class Solution
{
public:
void solve(vector &a, int index,int s,int N,vector &ans)
{
if(index==N)
{
ans.push_back(s);
return;
}
//picking element from the index
solve(a,index+1,s+a[index],N,ans);
// s=s-a[index];aisa kuch nhi hoga s datastructure nhi hai
//s ek simple variable hai samjha kuch nhi krna hai //decreasing the sum //simple backtrack
//pick notpick ka function easily call ho jayega samjha be
solve(a,index+1,s,N,ans);
}
public:
vector subsetSums(vector a, int N)
{
vectorans;
int index=0;
int s=0;
solve(a,index,s,N,ans);
sort(ans.begin(),ans.end() );
return ans;
}
};
Can be done in 3 ways [Bit manipulation, DP, Recursion]
Dp wont be possible as you need to print sums so you need to go to the depth always.
@@takeUforward Thanks for the mention bro
void dfs(vector &nums,vector &ans,int idx, int sum){
if(idx>=nums.size()){
ans.emplace_back(sum);
return;
}
// take
dfs(nums,ans,idx+1,sum+nums[idx]);
// not take
dfs(nums,ans,idx+1,sum);
}
public:
vector subsetSums(vector arr, int N)
{
vector ans;
dfs(arr,ans,0,0);
return ans;
}
Sort array in reverse order and do not take first and next call for take this way we get sum in inc order automatically..I am assuming all elts to be distinct..tc 2^n and SC is 2^n
Submitted successfully w/o sorting the result array.
2:20 GFG edited their expected space complexity
Hey Striver, Big fan and thank you for the amazing series, but in this question, we are asked about subsets and what you have explained is the solution for subsequences. In your video on subsequences, you had explained the difference between subsets and subsequences - "Subsequences can be contiguous as well as non-contiguous but subsets are always contiguous". This point can also be observed if we go to the problem link and see the examples mentioned.
Thanks striver. you made understanding so easy. thanks brother
Thanks a lot , i did this question all by myself becoz of your videos and your guidance , thanks a lot
best think of striver bhaiyya videos is promotion tell (time) so we can skip promotion easily every youtuber have to do this
you are doing amazing job ! keep up good work!
Here why we are not subtracting the sum while backtracking
Because we passed in the params!
do we even need to sort the array ,as it is not asked in the question?
I do think so that the time complexity of this approach would be O(2^nlog(2^n)) = O(n* 2^n). Please have a look at my code below, it is accepted on gfg and I think it is having time complexity O(2^n) only, please correct me I am wrong. The idea is still similar to either pick an element or not pick the element but we are only pushing sum+arr[n-1] value into the vector. Also, the recursive function will not consider of the case when no element is picked hence we have to push_back(0) into the vector at the very beginning.
void subSum(vector &arr, int n, int sum, vector &s) {
if(n == 0) {
return;
}
s.push_back(sum+arr[n-1]);
subSum(arr, n-1, sum, s);
subSum(arr, n-1, sum+arr[n-1], s);
}
vector subsetSums(vector arr, int N)
{
vector s;
s.push_back(0);
subSum(arr, N, 0, s);
return s;
}
why r we not removing here like we did in other problems
Please try to upload video daily and love your videos and explanation too much
Without sorting also all testcases passed for me in GFG.
Thankyou so much for great content Striver
Sorting isn't required, driver code is automatically sorting our array
Very Nice Lecture
class sol
{
public :
void func(int index,int sum,vector&arr,int n,vector&sumset)
{
if(ind==n)
{
sumset.push_back(sum);
return;
}
// pick
func(index+1,sum+arr[index],arr,n,sumset)
// not pick (sum not update)
func(index+1,sum,arr,n,sumset);
}
public :
vector sumset(vector arr,int n)
{
vector sumset;
func(0,0,arr,n,sumset);
sort(sumset.begin(),sumset.end());
return sumset;
}
};
can we store ans in a multiset and covert to vector and return.
By the way thank you very mush for this playlist.
whats the difference between recursion of subsequence and subset , isn't both of them same
Note: You don't need to explicitly backtrack here because the recursive stack itself takes care of the variable sum's state!
I think code is written wrong
Because we have to backtrack also
So sum should be subtracted before another recursive call
We pass sum+arr[i] to next function call when picking the current element and do not change the value of sum itself, so when going for not picking recursive call we just pass sum.
I guess Time Complexity can be reduced significantly!!
Instead of sorting the result array of size of size 2^n we can sort the input array of size of size n. And while picking instead of pick, FIRST perform NOT pick THEN pick
class Solution{
ArrayList subsetSums(ArrayList arr, int N){
Collections.sort(arr);
ArrayList result = new ArrayList();
subsetSums(0, 0, arr, result);
return result;
}
void subsetSums(int i, int currSum, ArrayList arr, ArrayList result) {
if(i == arr.size()) {
result.add(currSum);
return;
}
//not pick ith element for sum
subsetSums(i+1, currSum, arr, result);
//pick ith element for sum
subsetSums(i+1, currSum+arr.get(i), arr, result);
}
}
Not really. for [1,2,3]. the subset sum for [3] will occur before [1]. So, the final answer would still be unsorted.
@@nileshchandra6435 can u please elaborate your point, as the code above passes all the test cases on GFG including [1,2,3] (as first I am performing NOT pick then PICK)
In the recursive fxn, why is the condition
if( ind == N)
and why not
if( ind == N-1) as we're using 0 base indexing ???
It is zero based indexing but on function call we are incrementing ind + 1 so it will return as n == ind
why have you not used sum = sum-arr[index] before 19 statement
We should not consider input and output in space complexity right then space complexity will be O(N)
Can't thank you enough for these videos!
i have an good resume sir ., i find no ways to join Directi for SDE
Can anybody Please clear my doubt is this question is similar to generating all subsets by picking or not picking approach
C++
class Solution
{
void func(vector arr, int N, vector &sums, int sum = 0, int i = 0)
{
if(i >= N)
{
sums.push_back(sum);
return;
}
func(arr, N, sums, sum, i + 1);
sum += arr[i];
func(arr, N, sums, sum, i + 1);
}
public:
vector subsetSums(vector arr, int N)
{
vector sums;
func(arr, N, sums);
sort(sums.begin(), sums.end());
return sums;
}
};
It's my solution, before watching Striver's solution.😁
Where's the link for the power set?
Just one confirmation i need incase of list we remove last element and incase of variable we just return it. It happens because of pass by value and pass by reference?
man, this is a banger, thank you so much for this
Here is the Java Code for Reference
ArrayList subsetSums(ArrayList arr, int N){
ArrayListl=new ArrayList();
backtrack(l,arr,N,0,0);
return l;
}
public static void backtrack(ArrayListl,ArrayListarr,int n ,int i,int sum){
if(i==n){
l.add(sum);
return;
}
backtrack(l,arr,n,i+1,sum);
backtrack(l,arr,n,i+1,sum+arr.get(i));
}
Thank you sir
May be I am not able to understand the logic properly but to the extent that I understand I had one doubt when we don't pick any index then our sum is 0, and when we move to left of that than also our sum will be 0 so what I am trying to say is that we should be having duplicate values, can some one help me and let me know, if I am missing something
Are we allowed to return same sum multiple times in the array if sum of different subsets is the same
Thanks for the video. What if question is twisted a little bit and we have to find the smallest subset sum value which cannot be formed?
Ty!
That's a good question
Is 3 2 a sub set ? coze if the sum is 5 we will get this in the result 3 2 which is not a sub set of 3 1 2
so, in subsequence for picking, we are removing one element (last element) and then we go for not picking, but here we are not removing because sub-set means a continuous array. is this the correct reason? can anyone tell?
got it, i was bit confused before, here we are directly doing sum, not maintaining any separate ds for adding and removing elemenrs
Crisp clear explanation 👍