L8. Combination Sum | Recursion | Leetcode | C++ | Java
Vložit
- čas přidán 7. 02. 2021
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem Link: leetcode.com/problems/combina...
C++/Java Code: takeuforward.org/data-structu...
Get all the free classes schedule by experts in one place: unacademy.cc/daily_learning
INTERVIEW 2021: Concise Track to Clear Product Interviews taken by Arjun Arul and Riya Bansal (Preview Available)
unacademy.com/batch/interview...
Check out the star educators here: unacademy.cc/EducatorYT
Use code TAKEUFORWARD for unlocking free classes and 10% discount on subscription
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
C++ code: github.com/striver79/SDESheet/blob/main/combinationSumC%2B%2B
Java code: github.com/striver79/SDESheet/blob/main/combinationSumJava
Instagram for Live sessions: instagram.com/striver_79/
Good explaination 👍
Please check out...!!!
if we add one OR condition in the base condition as if(ind == arr.size() || target == 0), keeping rest of the code same, we get the right answer but in the less recursive calls. Because sometimes we get the target before reaching the last index, so once we get the target we need to stop at that moment and no need to check for further elements. As it's OR, once the base condition is satisfied, again inside that we need to check whether (target == 0) and confirm.
Here is the code :
public class RecursionEx
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
List answer;
System.out.print("Size of array : ");
int n = in.nextInt();
int[] num = new int[n];
System.out.println("array elements : ");
for(int i = 0; i < n; i++)
{
num[i] = in.nextInt();
}
System.out.print("Enter target : ");
int sum = in.nextInt();
answer = result(num, sum);
for(List i : answer)
System.out.println(i);
}
private static void combSumk(int i, int[] num, int s, List answer, ArrayList arr)
{
if(i == num.length || s == 0)
{
if(s == 0)
answer.add(new ArrayList(arr));
return;
}
if(num[i]
can you please give link of SDE sheet shown at the start of video lecture?
@@aashritamutkiri5071 what if the rest of the array has 0 in it,could miss one of the solution there!!
by doing all these i have developed logic and submitted this problem and got accepted. That was the first time, even a small problem i will make mistakes.
But now, i am improving. Thanks bhaiya for doing this and sharing your knowledge to everyone
Bro can u explain me the time complexity?
@@saunaknandi1814 17:43
@@saunaknandi1814 bro for that u need to see recursion tc first
@@saunaknandi1814 whenever recursion is used without memoization and we have choices >1 for a particular element
the time complexxity will be always exponeential correct me if im wrong
if we pop the ds then why we not modify target , target also should increase ??
Sir, I have watched many youtube channels for recursion, and all of them claim that they are the best in youtube, you'll learn to think recursively, blah blah blah... But as I have started watching your playlist of recursion, I got a very clear idea about recursion. Your way of explaining with recursive trees is the best thing I found anywhere online. It just resonates with our brain and now I can think RECURSIVELY. Thank you and keep making such amazing videos..
Striver bhaiya should be in the UN protected list❤.
Means?
💯💯😂
@@willturner3440 United Nation's Heritage.
No I don't think so it fairly easily problem if u r consistent with these problems, however i am not questioning his hardwork tht led him here
It is the first time I'm able to understand recursion so clearly. Thank you so so much 💗💗
How do you identify a good teacher.. When he explains each and every step so clearly and makes his students to think towards the solution instead of typing the solution and asking them to memorise it. You are the best Striver Bhai!!!!
Can you please tell me why are we doing -
ds.pop_back();
in the "if" condition itself....why cant we do this after "if" contion.???
@@202_b_ashishojha8 Draw a recursion tree and you'll find that we're only poping_back the item when the recursive function for same index is returning... dry run with some tweak i.e. putting the pop_back() outside the IF statement.. it will be more clear then.
You are awesome! Feeling confident in recursion now. Thanks a million!
This guy made my path to learn recursion easier.The way he explain is quite commendable. Thank you brother ❤
I watched the video till 7:25. It gave me an intuition of what could have been done, I explained this same approach to myself again and tried to code .... and damn ...I got the answer....
There were repeated entries in my answer set, but still .....from not being able to code backtracking problems to actually solving one to some extent .... feels really good
Bro can u explain me the time complexity?
Same i watched till 5 minutes
how only unique combinations are formed ?
@@ulhasyawatkare9697 did u get it? Struck der only
The way you teach difficult things in simple manner is just awesome bhaiya....♥️♥️♥️♥️
another lecture of recursion series ..another day of falling in love with striver's awesome explanation skill...i was like how man??!! how come someone sooo good at transfering knowledge to the community!! ❤️❤️❤️❤️🙌🙌🙌
You are the best. I have always found myself getting confused in recursion. But now I think I am getting it. Thank you Striver!
how only unique combinations are formed?
@@ulhasyawatkare9697Because we are only moving forward while fixing a value. As you see there is no "index-1" parameter.
Striver bhaiya has an another level of explanation. Understood every single words and entire approach🔥💥
best explanation on youtube
Thankyou for the lovely content
Legend is back, with another mind-boggling video🔥
Shandaar Solution bataya sir maja aa gaya,aise hi aasani se samzhate rahiye,thankyou very much
striver bhaiya ur way o teaching is so lovely and upto point that before i was scared of recursion and dp but after learning from you i solved this question in exact the same approach as u without watching the video thank you sm 🌟🌟
grateful to u for providing an easy to understand solution.
This is the same as of unbounded knapsack along with printing all psbl combinations.
Great explanation bhaiya,, love the way u teach❤💯
Thanks striver.. after watching Combination sum video, I was able to solve all its other three variations given on leetcode (Combination sum, Combination Sum II, Combination Sum III, Combination Sum IV) all by myself. Thanks a ton!
in the java code(line 6) if we write ans.add(ds) output showing empty list..why? and why he used ans.add(new ArrayList(ds));.....please help me
@@tridibsamanta6549 in my view function sign of Combination declare list so if we have to add element in it we have to declare its type like arraylist
how only unique combinatios are formed ?
sir if we keep the ind fixed, then it might even happen that ind remains fixed yet ind!=arr.size(), in that case if we want to do ans.push_back(ds), then how will it be possible since we have already defined the condition that ind==arr.size() , shouldn't we put an OR in the topmost 2 if statements?
Hi Striver. Your content is super amazing. Can you please make a backtracking solution video on Gray Code question of LeetCode?
15:00- recursive tree
19:00-time complexity
23:34-code
Thenku shweta ji🙏
Thanks!!!!! 🙏
what a rubbish
if you have come to see concept then you should have complete the full video.
these timestamps are all rubbish
Bhai tujhe microsoft mai job lagegi
For space complexity analysis you should not take input or output into acount. So space complexity is simply linear in target (callstack which is at max target plus the combination array which is at max also target). Space complexity = O(2*target) = O(target).
Thanks bhaiya for Providing this wonderful resource continue this good work for the people who need it
Excellent video bhaiya u will really take us forward thanks alot🙏❤
Wow explanation, literally mind blowing!
Thank you bhaiya for this wonderful explaination 😄 Now recursion is crystal clear.
Hats off to you bhaiya
Best explanation on Recursion .......we can feel what is happening not just learn the pattern of codes in mind
if we add one OR condition in the base condition as if(ind == arr.size() || target == 0), keeping rest of the code same, we get the right answer but in the less recursive calls. Because sometimes we get the target before reaching the last index, so once we get the target we need to stop at that moment and no need to check for further elements. As it's OR, once the base condition is satisfied, again inside that we need to check whether (target == 0) and confirm.
Here is the code :
public class RecursionEx
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
List answer;
System.out.print("Size of array : ");
int n = in.nextInt();
int[] num = new int[n];
System.out.println("array elements : ");
for(int i = 0; i < n; i++)
{
num[i] = in.nextInt();
}
System.out.print("Enter target : ");
int sum = in.nextInt();
answer = result(num, sum);
for(List i : answer)
System.out.println(i);
}
private static void combSumk(int i, int[] num, int s, List answer, ArrayList arr)
{
if(i == num.length || s == 0)
{
if(s == 0)
answer.add(new ArrayList(arr));
return;
}
if(num[i]
Hey, can you please let me know why my modification isn't working:
class Solution {
public:
void findComb(int index, int target, vector &ds, vector &res, vector candidates)
{
if(index == candidates.size())
{
if(target==0)
res.push_back(ds);
return;
}
if( target == 0)
return;
if(candidates[index]
@@sakshamchaturvedi under if(target==0) add res.push_back(ds) and then return
WE can also sort the original array first and now complexity reduces further since if the target equals our combination we should not be calling the not pick function anymore because that would only tend to increase the sum but in case if target less than sum then we should be calling both,pick and non pick
Yes right...we can add one more base case... no need to move further if target becomes 0
The solution you provide will only work if array elements are positive integers. Say it contained 0 or non-negative integers, then even if target=0 before index=n, we can still find a value which is positive and negative after index in the array. We could also have 0 's in the array which would give much more combinations such that sum=target.
Best possible explanation for this problem ever!!!
I love your way of explaining .Really love u man .
Thank you for such clear explanation!
I was able to solve the problem for the first time without any help..thanks striver
We can also add a condition before reaching the last index to check for target==0. As this can avoid unnecessary recursion calls. Btw great video bhaiya ❤
same thing i was thinking thanks bro
Hey Striver, thank you so much for this video but I have a doubt... When I was missing the = sign from line 11 of cpp code, the output wasnt printing anything and just by converting < to
how did you got it i;m still getting wrong answer
thanks bhaiya all my doubts got cleared in this video great content keep educating us 😀👍🏽
Bro can u explain me the time complexity?
Thanks for explaining so well man.
Amazing Explanation..Thanks Striver!!!
LeetCode: Combination Sum(39.) ->
Code:
class Solution {
public:
void helper(int i, int target, int SumTillNow, vector&candidates, vector&subset, vector&ans){
if(SumTillNow==target){
ans.push_back(subset);
return;
}
if(SumTillNow>target) return;
if(i>=candidates.size()) return;
//pick
SumTillNow+=candidates[i];
subset.push_back(candidates[i]);
helper(i,target,SumTillNow,candidates,subset,ans);
SumTillNow-=candidates[i];
subset.pop_back();
//not pick
helper(i+1,target,SumTillNow,candidates,subset,ans);
}
vector combinationSum(vector& candidates, int target) {
vectorsubset;
vectorans;
helper(0,target,0,candidates,subset,ans);
return ans;
}
};
thank you
Thanks... I was stuck on this code for the past three days...... The code given in the documentation just didn't work...
How it gonna work if the given array of integers (candidates) also contains negative values and the target sum = 0?
Finally , bhaiya is back, bhaiya how's ur health now?
If I am using string and then at last I am copying data into arraylist will it remove the k factor from time complexity?
It's like an adiction , I want to see ur lectures on a repeat
best explaination found on whole youtube
Striver bhaiyya your explanation was on point.I followed the recursive tree approach and could code it myself but when I saw your approach I was not quite understanding why you removed the element from the ds .
My code(Inspired by i/p o/p method)
class Solution {
public:
void solve(int index,int target,vectorip,vectorop,vector&ans,int n)
{
if(index==n)
{
if(target==0)
{
ans.push_back(op);
}
return;
}
vectorop1=op;
vectorop2=op;
if(ip[index]
proposed by: Aditya Verma
@@rajkumarchaudhary3903 yes I/p o/p method
class Solution {
public:
void findCombination( int ind, int target, vector& arr, vector &ans, vector&ds)
{
if(ind == arr.size()){ // arr is given vector
if(target == 0){
ans.push_back(ds);
}
return;
}
// pick up an element
if(arr[ind]
hey i am getting stack overflow error :(
For non-duplicates, we check each value twice...so time complexity becomes O(2^n).
But in this case, we r checking each value k times, so it should be O(k^n) ?
Yup you're right. He was wrong to say 2^t.
awesome man...easy to understand..thanx
First my python code returned [ [ ], [ ] ]. After seeing your java code snippet ans.add(new ArrayList(ds)) , I rectified my mistake. Thanks bro. ✌🏾
Great
can you please share you python code. i am also getting same answer and not able to find where i am doing wrong
Bro... the problem with my code was when index==n and target==0, I did ans.append(ds), the ans array is storing the reference of ds object. So, when ds changes in further recursions, the referenced values in ans array also changes. So, I did ans.append(ds.copy()). Storing a copy for ds array so that I don’t lose that particular combination. Hope it helps. If you are still stuck, I think @takeuforward Raj bro can explain it better.
@@shiva2526 no no. i got your point. i was also doing same mistake. Thanks for your help brother
please share your python solution .
Bhaiya!!!❤️❤️❤️❤️
OP explanation!!🙏🏽🙏🏽
You are a life saver. Can't thank you enough.
do anyone have any idea why in the base condition we add new ArrayList(ds) instead of adding ds only cause ds itself is an arrayList?
Sir do add this condition
if(arr[ind]
actually it is provided in the Combination sum type problems that the elements will never be 0
recursion makes solutions to appear so easy :)
I believe there can be an improvement on top of this, where we can sort the candidates list itself and put the condition in base to return in case the candidates[idx] > target
thanks bro for this amazing series ❤
what's the runtime and memory usage of above code in Leetcode?
you are great my brother... I am really falling in love with your style ❤.
Is it possible to modify the subset-2 logic(unique subsets) to satisfy this problem? If yes, pls tell me how.
I think push_back() works in constant time complexity. Please correct me if I am wrong. Great explanation btw!
Yes it does
Bro can u explain me the time complexity?
What's the time complexity for DP based solution? Is this better than DP?
Really Raj you did explain very very well
This was epic. Thanks a lot bro :)🤩
Welcome back raj bhiya 🥳
Awesome explanation .. :) can't it be solved using DP?
Hello, do we need to add the arr[ind] value after removing the value when the recursive call returns? Since, such problems follow the pattern append, add, remove and subtract. Thanks!
we don't need to add arr[ind] here like in previous video, we're subtracting here from the target and checking if it reaches 0
Thank you striver bhaiya for such amazing explanations.
class Solution {
public:
void findcombination(int index,int target,vector &arr,vector&ans,vector&v)
{
if(index==arr.size())
{
if(target==0)
ans.push_back(v); //liner time (adding one data struc to another)
return ;
}
//pick the element
if(arr[index]
Very nice and clear cut explanation
Hi sir, if it's at all possible for you to share iterative approach along with recursive approach it would be great. Even if you just post the code and not explain is also fine.
Awesome video... clearlyyy undesrstoooooooood!!!
Bhaiya, What if I call the second recursion before the first one, then, I would not have to remove the element back from the ds, right?
Is there any particular reason for the order of recursion call? that is the recursion when picking element first and then, the recursion for not picking the element?
yes.if u picked a number in one recursion then u should avoid it in some recursion calls as it will give duplicates so the order of recursion matter
Tough questions feels easy after watching your video
awesome video bhaiyya but i have one doubt here, when we are getting target =0 then why we are going in iteration again, we can just return from there. we can change the code like, removing greater than equals to sign and put only > sign and in next if condition put equals to sign and if that satisfies then simply return from there
If the next element is zero then one possible combination is 2,2,3,0 in case of target =7
otherwise we will skip it if we return on target ==0
why we take vector ans? Why 2D vector?
Read the questions carefully. We have to return a vector of all possible vectors. something like this. [ [ 2,2,3 ] , [ 7 ] ].
Good Day :)
GREAT EXPLANATION!!!!!
Awesome explanation brother.Keep it up
Bro can u explain me the time complexity?
can someone please tell me what does this line of code in JAVA ans.add(new ArrayList(ds)) do?. Thanks in advance
Bhaiya, the way you explain is amazing, you are doing a really really really amazing job for all of us, keep posting so that we can learn, thanks a lot
Bro can u explain me the time complexity?
how do you avoid same combination in answer multiple times, like in subsequent recursive calls it find [2,2,3] as solution more than once and adds it to ans even though its not unique...
why did you write target==0 inside index==arr.length? What if the sum is reached before the whole array is traversed? Eg [1,2,3] target = 3. So ds=[1,1,1] makes 3 and index is still 0. so, it will make unnecessary calls because we need index to be 3. I think we can write if(target==0){ add; return;} separately.
Why do you consider answer storing data structure in space complexity? That is something needed by question.
Great explaination bhaiya !
Thank You so much sir, You're Best
Easy approach like power set
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res=[]
def dfs(curr,i,tot):
if tot==target:
res.append(curr.copy())
return
if i>=len(candidates) or tot>target:
return
curr.append(candidates[i])
dfs(curr,i,tot+candidates[i])
curr.pop()
dfs(curr,i+1,tot)
dfs([],0,0)
return res
got more clearance on copy module in python thank you.
@@anmolojha6851 This copy method saved my life. Wasted 2 hours thinking what is wrong
I have used the loop and single recursion call
Shouldn't the time complexity be O(2^k) for the recursive operations since the maximum take and not take operations can be k.
At timestamp 20:00, time complexity is told to be 2^t * k, here, it is clear that t > n, but what is 't' exactly ? I mean, it isn't number of elements. What is it ?
t mentioned int the T.C is the target value which can be achieved by let say 1 picking t times in worst case scenario, so every element has t options to choose and their are total n elements so T.C will be t^n * k where k is average length.
i hope it helps. Mention it if i am wrong.
alag he level k explanation hai bhai k
At the very beginning I got the logic as it is similar to the prev question and coded on my own
Bro can u explain me the time complexity?
class Solution {
public:
void findCombination( int ind, int target, vector& arr, vector &ans, vector&ds)
{
if(ind == arr.size()){ // arr is given vector
if(target == 0){
ans.push_back(ds);
}
return;
}
// pick up an element
if(arr[ind]
hey this is my code, i am getting an error, can you pleasee help
Are we suppose to Discuss Iterative solution as well in the interview, can the interviewer say to solve this with iterative approach ??
Nah does not happens
we can sort the input array and if we not pick than once no need to check further
Hey great lecture♥
i want to ask
why using -> ans.add(new ArrayList(ds)); works fine but
using -> ans.add(ds); gives me empty ArrayLists?
even when i declared it and then passed as a parameter instead of creating object inside findCombinations( ) method in the main function?
I had the same query as well. In cpp they just pushed the datastructure ds.
java works by reference, that is the reason, at the end you would have popped out all
Java doesn't have pointers like C++
-> (this arrow operator) works with Pointers only. Hope this helps you
You need to create a COPY of ds before adding it. As you see ds keeps getting passed on as an argument and keeps getting modified. If you just add ds, all the modifications you make to ds get reflected in the final list.
if you directly add ds, what you actually add is the address of ds. In the following calculation, ds will continue change, so the content in the address will change. But if you add a new ArrayList, it won't change anymore.
hii striver thanks for amazing video , just having doubt that can't we further reduce recursion calls by taking out target == 0 condition outside of if as a second base condition ?
Same doubt
@@yeswanthh5068 same, also why did we done this ans.add(new ArrayList(al));
not ans.add(al);
Shouldn't be there is another base case like when target is 0 irrespective of n, it should return?
Why to check till index==length? We can return if the target reaches zero or in the second condition if the trarget
Is it necessary to consider auxiliary space for storing combination?
Nah, since its interview, it does not matter if you clarify it to the interviewer..
This code will break if you have zeros in your input. thanks for the great expalination.
I don't get it .....😢😢 after pop_back why we are not updating our target value, somebody please explain