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.
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
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.
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 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)).
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 🙏♥️🤩🔥
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 ..
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; }
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)); }
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.
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.
@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 ...
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 ❤
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 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.
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
📢🔥🔥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
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?
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 had a question for you Striver or any one in comments section Sum+=arr[ind] Func(ind+1,sum,n,subset) Sum-=arr[ind] Func(ind+1,sum,n, subset) Is this procedure correct? Correct me if I'm wrong
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
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.
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
class Solution { public: void subset_sum(int ind,vectorarr,vector&ans,int sum,int n){ if(ind==n){ ans.push_back(sum); return; } // case to pick an element to be added in sum subset_sum(ind+1,arr,ans,sum+arr[ind],n); subset_sum(ind+1,arr,ans,sum,n); } vector subsetSums(vector arr, int n) { vectorans; int sum =0; int ind =0; subset_sum(ind,arr,ans,sum,n); return ans; } };
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.
//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; } };
agar hmlog given array ko phle hi sort kr de decreasing order me aur not pick wala function call pick wale function call k phle rkh de, to hme apne ans ko alag se sort krne ki jarurat nahi pdegi, and aise hm 2^n*log(2^n) T.C ko n*logn se optimise kr skte h.
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
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?
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
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
sorting the given array in decreasing order and doing not pick before pick will reduce the time complexity a little as the final answer will not need sorting
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; }
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.
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); }
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?
ruclips.net/video/b7AYbpM5YrE/видео.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!!
were you from VESIT??
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.
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
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.
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.
The first recursive approach which I understood clearly.. Thank you so much sir.
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
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 🙏♥️🤩🔥
First Viewer, just wanted to say, You're doing amazing job! Keep up the good work!
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 ..
I have made this question from myself using both iterative and recursive approach thanks striver from bottom of my heart ❤
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
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
Link for Power set Video mentioned at 3:15 :
ruclips.net/video/b7AYbpM5YrE/видео.html
Moving to L11 , this was an easy one 👍
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.
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.
@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.
@@shashankdixit92 first we have to sort given array in descending order and then selecting not picking
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 ❤
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😃
Understood bro i just understood the method without pseudo code and wrote program myself. Great explanation
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!!!!!!
Best explanation i have found here in this video thanks a lot for ur hard work nd keep doing
he is a legend for the first time I have solved a recursion question myself
Thnaks striver, did all that by myself by just seeing half the approach.
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
Thank you for using real english. I subscribe your soul 👍
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
Bhaiya mtlb kaise btaun apne to kamal kardia
ye question mne khud try kia aur first attempt m kardia
Apse padhkar maza agya.
22:24 c++ code
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
thank you bhaiya, for your awesome informative videos of most important DSA question, aap jldi thik ho jao ......
It can be done without sorting if we do not pick first and the call the pick recursion call.
you are doing amazing job ! keep up good work!
UNDERSTOOD... !!!
Thanks striver for the video... :)
📢🔥🔥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
one of the best explanation!!!!!!!!
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?
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.
solved in 8 min just by reading problem statement ❤🔥❤🔥❤🔥
congratulations bhaiya apka google me hogya na!, Main bhi aa rha hu jldi hi milte hai
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 had a question for you
Striver or any one in comments section
Sum+=arr[ind]
Func(ind+1,sum,n,subset)
Sum-=arr[ind]
Func(ind+1,sum,n, subset)
Is this procedure correct?
Correct me if I'm wrong
yeah absolutely correct
do we even need to sort the array ,as it is not asked in the question?
If someone does this tracing for merge sort till the end his confidence increases a lot in recursion
thnks bhaiya i was able to do combination sum 3 on my own only because of u
Thanks a lot , i did this question all by myself becoz of your videos and your guidance , thanks a lot
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]
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
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
Thanks striver. you made understanding so easy. thanks brother
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.
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 really afraid of this questions but when I see your video some magic happen
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.
class Solution {
public:
void subset_sum(int ind,vectorarr,vector&ans,int sum,int n){
if(ind==n){
ans.push_back(sum);
return;
}
// case to pick an element to be added in sum
subset_sum(ind+1,arr,ans,sum+arr[ind],n);
subset_sum(ind+1,arr,ans,sum,n);
}
vector subsetSums(vector arr, int n) {
vectorans;
int sum =0;
int ind =0;
subset_sum(ind,arr,ans,sum,n);
return ans;
}
};
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.
Crisp clear explanation 👍
man, this is a banger, thank you so much for this
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
//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;
}
};
C++ code at 23:50
Complexity analysis at 20:05
agar hmlog given array ko phle hi sort kr de decreasing order me aur not pick wala function call pick wale function call k phle rkh de, to hme apne ans ko alag se sort krne ki jarurat nahi pdegi, and aise hm 2^n*log(2^n) T.C ko n*logn se optimise kr skte h.
Can't thank you enough for these videos!
The space complexity here will be of O(N) because that will be the depth of the recurs ion tree.
Understood ❤
understood, thanks for the perfect explanation
why have you not used sum = sum-arr[index] before 19 statement
Thankyou so much for great content Striver
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
Please try to upload video daily and love your videos and explanation too much
whats the difference between recursion of subsequence and subset , isn't both of them same
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?
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
best think of striver bhaiyya videos is promotion tell (time) so we can skip promotion easily every youtuber have to do this
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
Good to see you after long time bhaiya
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
2:20 GFG edited their expected space complexity
Are we allowed to return same sum multiple times in the array if sum of different subsets is the same
sorting the given array in decreasing order and doing not pick before pick will reduce the time complexity a little as the final answer will not need sorting
Arey sort to kia na then how will it reduce TC?
Where's the link for the power set?
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;
}
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;
}
Very Nice Lecture
Where can I find the powerset solution link?
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.
Well explained bhai👍
he is the definition of handsome with brains!!
Very Helpful 🙏
Sorting isn't required, driver code is automatically sorting our array
thank you bhaiya 😇😇😇😇
Submitted successfully w/o sorting the result array.
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);
}
can we store ans in a multiset and covert to vector and return.
By the way thank you very mush for this playlist.
Note: You don't need to explicitly backtrack here because the recursive stack itself takes care of the variable sum's state!
Can we reverse the resultant subset sum array?