Summary: 1. Combination Sum 2 is a question of Subsets-II, which was generating Unique subsets, and Combination- I where we need to generate a subsets whose sum is equal to TargetSum. To avoid duplicate elements, we need to sort the given array first then only we can use the logic as we discussed previously of generating Unique subsets with duplicate elements. 2. The only difference is that we can't keep choosing an element as many times as we want. We can choose an element only once. 3. So what we will do here is, we use the knowledge of Subsets-II and Combination Sum -1 to solve the question. 4. The bases cases are very simple: a) if(currenrSum == targetSum) put the subset in your ans[][] vector and return. b) if (currentSum > targetSum) We can't get the targetSum, so we should return c) if(i >= arr.size()) We have traversed the entire array so we should return. 5)We then pick the ith element, put it into our subset[] vector and increment sum as sum += arr[i] and call Recursive function with i+1 6) On returning, we need to backtrack, and put the element out of subset vector and bring currentSum to its original value. 7) Now to avoid duplicate elements, we start traversing through the subset till arr[i] == arr[i+1] 8)After that, we apply the condition of don't pick, so i+1 but currentSum remains the same. Time Complexity: O(2^N) [ Because we are always moving to the next index so it can be O(2^N) , if target is equal to sum of all array elements as well] Space Complexity: O(N) [ It's equal to the height of the Recursive tree, so it's O(N)]
you won't believe but after watching the whole playlist for 2-3 times along with playlist from other creators on backtracking I have witnessed a slight improvement in my intuition and logic building.....now when I pick a question on backtracking, even if I cannot fully solve it but at least I predict the strategy that should be used for question and few sidecases......all thanks to you FRAZ BHAI......
your way of teaching is extraodinary man.first you explain the problem very well it creates the whole story of a problem and then you start coding so it will be very easy for us to understand the whole code very easily. becuase of this way of teaching we are able to understand these complex problem very easily. Thank you so much for teaching us free with such a very very good content.
Mujhe lga tha aaj video nhi aaegi kyoki main channel par ek video aae aur aaj recursion contest bhi hai But here comes the lecture, we are consistent 🤩🤩
Awesome lecture,❤small edition if we just do help(index,arr,subset,powerset,sum+arr[index],target) then no need to take tension of decrementing sum. after watching the next video, I am editing my comment , Fraz bhiyaa talked about the same thing, kudos.💖
JUST HAVE TO TAKE CARE OF THE DUPLICATE. TOOK ME 20 MIN TO UNDERSTAND THIS. SO UPLOADING THIS HERE FOR SENSE OF COMPLITION :) void helper(int i, vector& arr, int target, int sumTillNow, vector &ds, vector &ans) { if(sumTillNow == target){ ans.push_back(ds); return; } if(i >= arr.size()) return; if(sumTillNow > target)return;
// skip the ith element helper(i+1, arr, target, sumTillNow, ds, ans);
// take the ith ele sumTillNow += arr[i]; ds.push_back(arr[i]); helper(i+1, arr, target, sumTillNow, ds, ans); sumTillNow -= arr[i]; //BACKTRACKING ds.pop_back(); //BACKTRACKING
Logic: For every element in the array, we have two choices, either to consider it or not to consider it if we consider the element we can go to next element and we can consider it or not(keep adding the current element to sum) if we ignore the element , we no longer consider the same element in future so if we encounter the same value we have to skip or ignore it(we can done this by using the while loop condition) Code: def helper(i,a,b,sumTillNow,subset,ans): if sumTillNow == b: ans.append(subset[:]) return if sumTillNow > b: return if i >= len(a): return #considering the ith element sumTillNow += a[i] subset.append(a[i]) helper(i+1,a,b,sumTillNow,subset,ans) sumTillNow -= a[i] # Backtracking subset.pop() # Backtracking
while i+1 < len(a) and a[i] == a[i+1]: i += 1 #not considering the ith element helper(i+1,a,b,sumTillNow,subset,ans) a = [10,1,2,7,6,1,5] b = 8 a.sort() ans = [] subset = [] sumTillNow = 0 helper(0,a,b,sumTillNow,subset,ans) print(ans)
In the leetcode this solution gives memory Overflow for leetcode solution given code is works fine: class Solution { public: vector combinationSum2(vector& candidates, int target) { sort(candidates.begin(), candidates.end()); vector < vector < int >> ans; vector < int > ds; findCombination(0, target, candidates, ans, ds); return ans; } void findCombination(int ind, int target, vector < int > & arr, vector < vector < int >> & ans, vector < int > & ds) { if (target == 0) { ans.push_back(ds); return; } for (int i = ind; i < arr.size(); i++) { if (i > ind && arr[i] == arr[i - 1]) continue; if (arr[i] > target) break; ds.push_back(arr[i]); findCombination(i + 1, target - arr[i], arr, ans, ds); ds.pop_back(); } } };
Notes: The problem is very similar to subset 2 problem, we'll just have to limit recursion based on the value of sum, and add current array to result in case sum is zero. Time Complexity: O(2 ^ n) (Worst case when all elements are unique and exact sum is never reached) Space Complexity: O(N) (excluding space taken up by result array)
Episode 13 completed!🔥 Combination sum 2 Here,its similar to previous problem but here the elements will be repeated so we need to avoid generate duplicate subsets for this we are using the approach we used in subset 2 problem ie if we are ignoring an element we are ignoring the all the other the occurrences and to do this we use while loop and increment i and incrementing sum variable and we are comparing it with target sum!
first we include element in our sum by pushback in vector sum then we pop back the element -> explicit backtracking as in sum 2 we have condition to take element once=>> so we use while loop till a[I]==a[I+1] we jump same element by i++; at last we skip the element by calling same function but i+1 ;;
My summarization : It is almost same as that of combination sum where we took a sumTillNow variable and if we pick the ith element , we will add it to the sum variable and push it to our subset vector and call recursively the helper function for the i+1th element and then we have to backtrak our answer by deleting taht ele from the sum and poping it out of our subset vector then we will call for the not pick case with ith element recursively and moving the base conditions , if our sum is equal to target , the push it to answer vector and return and if i exceeds n, then return and if sum exceeds target then also return
Bro how to get an internship for a 2nd year student I mean where and how to apply because we don't have any specific experience in the role and the Company how to select us....bcoz sab koi bol dete hai ki ye karlo woh karlo interest pai koi v skill pey sikh kar ke internship kar lo but koi ye nahi batata ki kaise apply kare...itni bheed main hum kaise uss company Mai as a fresher internship paye... Can you make a complete separate video in this topic...🥺🙏
Sir, Self Solved, This problem is solved by using recursion, all test cases pass but submit time 11 test cases is not passed (only one or last test case). This case also passes but one subset (6 8 16 ) is extra generated so not passed this test case mine.
Codes will be available after few mins, as of now give it a try yourself ☺
Ok sir
Summary:
1. Combination Sum 2 is a question of Subsets-II, which was generating Unique subsets, and Combination- I where we need to generate a subsets whose sum is equal to TargetSum. To avoid duplicate elements, we need to sort the given array first then only we can use the logic as we discussed previously of generating Unique subsets with duplicate elements.
2. The only difference is that we can't keep choosing an element as many times as we want. We can choose an element only once.
3. So what we will do here is, we use the knowledge of Subsets-II and Combination Sum -1 to solve the question.
4. The bases cases are very simple:
a) if(currenrSum == targetSum)
put the subset in your ans[][] vector and return.
b) if (currentSum > targetSum)
We can't get the targetSum, so we should return
c) if(i >= arr.size())
We have traversed the entire array so we should return.
5)We then pick the ith element, put it into our subset[] vector and increment sum as sum += arr[i] and call Recursive function with i+1
6) On returning, we need to backtrack, and put the element out of subset vector and bring currentSum to its original value.
7) Now to avoid duplicate elements, we start traversing through the subset till arr[i] == arr[i+1]
8)After that, we apply the condition of don't pick, so i+1 but currentSum remains the same.
Time Complexity: O(2^N) [ Because we are always moving to the next index so it can be O(2^N) , if target is equal to sum of all array elements as well]
Space Complexity: O(N) [ It's equal to the height of the Recursive tree, so it's O(N)]
Yes yes 🥰 i found your summary thank you so much bro..if u have time pls summary old ep..like 3-4-5-6 -7 if you want🥰!
@@emtiazahmed5333 Thank you for your comments. Will definitely do them after some time
Another level of confidence i have since I'm following this series
you won't believe but after watching the whole playlist for 2-3 times along with playlist from other creators on backtracking I have witnessed a slight improvement in my intuition and logic building.....now when I pick a question on backtracking, even if I cannot fully solve it but at least I predict the strategy that should be used for question and few sidecases......all thanks to you FRAZ BHAI......
The way u r showing us those mistakes really is helping me a lot,thanks a ton🙏☺️
your way of teaching is extraodinary man.first you explain the problem very well it creates the whole story of a problem and then you start coding so it will be very easy for us to understand the whole code very easily. becuase of this way of teaching we are able to understand these complex problem very easily. Thank you so much for teaching us free with such a very very good content.
Thanks a ton
Thank you for doing the copy paste, somehow I missed that last lecture and now went back to understand. You really understand your students.
I am gaining confidence with your series, also enjoying!
Thanks!
You are great bhaiya
Because those students who are not any source to afford learn Dsa
This Dsa course are really helpful
Placements 🙏🙏🙏
Mujhe lga tha aaj video nhi aaegi kyoki main channel par ek video aae aur aaj recursion contest bhi hai
But here comes the lecture, we are consistent 🤩🤩
Sir really really helpful now i started to understand the concept of recursion and also able to solve problems based on that. All thanks to y'a sir!!
Don't loose motivation bro
As these are educational videos. It takes time but pays off in long run
Ep 13 done ✅✅
Simple crisp clear 🙂
episode - 13 done , i was able to do this question on my own
Also hw problem done
thanks fraz bhaiyya
Sir your all videos are very good and your consistency is great
Was feeling down from last 2 days
But feeling high now 😊
Well explained!
Really loved the simple code, unlike other channels
Thanks Fraz bhai... I was able to solve this problem (through your hw problem link) yesterday just on the basis of your previous lectures.
Thankyou bhaiya for helping us learn this for free
Because choice of question is very good very confident after solving these without seeing ur code keep doing the awesome work❤❤❤❤❤❤
Awesome lecture,❤small edition if we just do help(index,arr,subset,powerset,sum+arr[index],target)
then no need to take tension of decrementing sum.
after watching the next video, I am editing my comment , Fraz bhiyaa talked about the same thing, kudos.💖
Done Understood❤✅ things are getting more clear as we are moving forward with the lectures
Thanks, #Fraz
#DSA #Recursion #Placement
thx fraz bhaiya for this recusion series. This series is a gem.......
Again another variation....priceless explanation and yes I am very much excited to complete recursion!!keep uploading bro 🔥🔥love you ❤️
Mistakes also helps in clearing things
JUST HAVE TO TAKE CARE OF THE DUPLICATE. TOOK ME 20 MIN TO UNDERSTAND THIS. SO UPLOADING THIS HERE FOR SENSE OF COMPLITION :)
void helper(int i, vector& arr, int target, int sumTillNow, vector &ds, vector &ans)
{
if(sumTillNow == target){
ans.push_back(ds);
return;
}
if(i >= arr.size()) return;
if(sumTillNow > target)return;
// skip the ith element
helper(i+1, arr, target, sumTillNow, ds, ans);
// take the ith ele
sumTillNow += arr[i];
ds.push_back(arr[i]);
helper(i+1, arr, target, sumTillNow, ds, ans);
sumTillNow -= arr[i]; //BACKTRACKING
ds.pop_back(); //BACKTRACKING
}
vector combinationSum2(vector& arr, int target)
{
vector ds;
vector ans;
helper(0, arr, target, 0, ds, ans);
return ans;
}
For finding the subset, order of elements in the array also matters, then why not the answer is changing when we are sorting the array
most underrated solution
wow such a wonderful explanation bhaiya....
Logic:
For every element in the array, we have two choices, either to consider it or not to consider it
if we consider the element we can go to next element and we can consider it or not(keep adding the current element to sum)
if we ignore the element , we no longer consider the same element in future so if we encounter the same value we have to skip or ignore it(we can done this by using the while loop condition)
Code:
def helper(i,a,b,sumTillNow,subset,ans):
if sumTillNow == b:
ans.append(subset[:])
return
if sumTillNow > b:
return
if i >= len(a):
return
#considering the ith element
sumTillNow += a[i]
subset.append(a[i])
helper(i+1,a,b,sumTillNow,subset,ans)
sumTillNow -= a[i] # Backtracking
subset.pop() # Backtracking
while i+1 < len(a) and a[i] == a[i+1]:
i += 1
#not considering the ith element
helper(i+1,a,b,sumTillNow,subset,ans)
a = [10,1,2,7,6,1,5]
b = 8
a.sort()
ans = []
subset = []
sumTillNow = 0
helper(0,a,b,sumTillNow,subset,ans)
print(ans)
#EP_13 completed
Consistency OP 🔥🔥🔥
Very clearly understood
because of this reason, I watch this lecture.
Homework problem done. Now recursion is no more tough
Best Backtracking series till now !!!!!!!
BEST EXPLAINATION.
Simple explanation wow✅
Great fraz bhai.....due to your consistency we are also consistent
In the leetcode this solution gives memory Overflow
for leetcode solution given code is works fine:
class Solution {
public:
vector combinationSum2(vector& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector < vector < int >> ans;
vector < int > ds;
findCombination(0, target, candidates, ans, ds);
return ans;
}
void findCombination(int ind, int target, vector < int > & arr, vector < vector < int >> & ans, vector < int > & ds) {
if (target == 0) {
ans.push_back(ds);
return;
}
for (int i = ind; i < arr.size(); i++) {
if (i > ind && arr[i] == arr[i - 1]) continue;
if (arr[i] > target) break;
ds.push_back(arr[i]);
findCombination(i + 1, target - arr[i], arr, ans, ds);
ds.pop_back();
}
}
};
Day 13
Aaj test tha aur mujhe laga aaj lecture upload nahi hoga
Hoga hoga lecture upload
@@dashundev1586 👍
Acha padha rhe ho ...lagge rahi time nahi h hamare paas bss agust tak k time h jaldi videos bana do bhai .... *💔
More Power to you!!!!
Thankyou so much bhaiya, for your hard work.
Another day another solution 😍
Very well explained
thanks for the video
#Day 13
This is what I Eagerly waiting for 🥳🥳
lecture 13 Done waiting for the next lecture 🤞🤞🤞🤞👌👌👌💛💛🖤❤
Well explained ✌️✌️
Commenting so that you can be motivated
Notes:
The problem is very similar to subset 2 problem, we'll just have to limit recursion based on the value of sum, and add current array to result in case sum is zero.
Time Complexity: O(2 ^ n) (Worst case when all elements are unique and exact sum is never reached)
Space Complexity: O(N) (excluding space taken up by result array)
Present bhaiya ✋ bhaiya ab aap ek din mai do videos upload krdo pdne mai mja aa rha hai
great explanation!!
Episode 13 done! 🔥🔥
acha padhate ho bhaiya ..aur padhao jaldi se jaldi
Bhaiya, if possible then please discuss the contest questions ,not the complete explanation just only the strategy.
Episode 13 completed!🔥
Combination sum 2
Here,its similar to previous problem but here the elements will be repeated so we need to avoid generate duplicate subsets for this we are using the approach we used in subset 2 problem ie if we are ignoring an element we are ignoring the all the other the occurrences and to do this we use while loop and increment i and incrementing sum variable and we are comparing it with target sum!
Keep making videos sir
great work bro
Lecture 13 Completed ☑
#dsabyfaraz☀
#recursionbyfaraz❤
Now done this one also 😉
Super content bro
first we include element in our sum by pushback in vector sum
then we pop back the element -> explicit backtracking
as in sum 2 we have condition to take element once=>>
so we use while loop till a[I]==a[I+1]
we jump same element by i++;
at last we skip the element by calling same function but i+1 ;;
day 13 done keep uploading videos
Good Video
Thank you again
I am running little late, will catch up by sunday
Great
Yes #first comment🥰
true inspiration
My summarization :
It is almost same as that of combination sum where we took a sumTillNow variable and if we pick the ith element , we will add it to the sum variable and push it to our subset vector and call recursively the helper function for the i+1th element and then we have to backtrak our answer by deleting taht ele from the sum and poping it out of our subset vector then we will call for the not pick case with ith element recursively
and moving the base conditions ,
if our sum is equal to target , the push it to answer vector and return
and if i exceeds n, then return
and if sum exceeds target then also return
when will you provide the solutions for contest questions
thank you sir
Thanks brother
Bro you are best
Please upload corrected and tested java code for all the lectures.
Thank you so much!
bhaiya aaj waley topic se related bhi contest mein aa sakta hain ???
why are you not making videos for another topics of dsa 😐
Reach++;
✌️💥
Done ✅
Consistency ++
Bro how to get an internship for a 2nd year student I mean where and how to apply because we don't have any specific experience in the role and the Company how to select us....bcoz sab koi bol dete hai ki ye karlo woh karlo interest pai koi v skill pey sikh kar ke internship kar lo but koi ye nahi batata ki kaise apply kare...itni bheed main hum kaise uss company Mai as a fresher internship paye...
Can you make a complete separate video in this topic...🥺🙏
❤️
Sir, Self Solved, This problem is solved by using recursion, all test cases pass but submit time 11 test cases is not passed (only one or last test case). This case also passes but one subset (6 8 16 ) is extra generated so not passed this test case mine.
thankyou
Sirr this problem on leet code iss getting wrong answer
feeling so bad, i just completed with todays HW problem successfully but in the contest, i didn't make it atleast one prblm , feeling so bad,
love
Bhai ye same solution leetcode par TLE De raha he !
i don't know why am i getting wrong answer although i am copying the same code you write😐
Second lol
C++ Code :
void helper(int i, int target, int sumTillNow, vector &arr, vector &ds, vector &ans){
//base case
if (sumTillNow == target){
ans.push_back(ds);
return;
}
if (i >= arr.size()) return;
if (sumTillNow > target) return;
//take
sumTillNow += arr[i];
ds.push_back(arr[i]);
helper(i+1, target, sumTillNow, arr, ds, ans);
sumTillNow -= arr[i]; //backtrack
ds.pop_back(); //backtrack
//not take
while (i+1 < arr.size() and arr[i] == arr[i+1]) i++; //to skip the repetation
helper(i+1, target, sumTillNow, arr, ds, ans);
}
vector combinationSum2(vector& arr, int target) {
vector ans;
vector ds;
int sumTillNow = 0;
sort(arr.begin(), arr.end());
helper(0, target, sumTillNow, arr, ds, ans);
return ans;
}