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/
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) {
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
@@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
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..
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!!!!
@@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.
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
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!! ❤️❤️❤️❤️🙌🙌🙌
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) {
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
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.
LeetCode: Combination Sum(39.) -> Code: class Solution { public: void helper(int i, int target, int SumTillNow, vector&candidates, vector&subset, vector&ans){
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!
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
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 ❤
Hey Striver, Your videos help a lot. I search for a problem name and add TUF in the front. If you have solved the problem even before video starts I'm happy. As I know if you have explained it I am going to understand it super well. Thank you so much for making these videos
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).
// Time: O(n ^ target/min(candidate)) // The same candidate can be used multiple times in the same combination, meaning the algorithm // can go deeper in recursion for each element. The depth of the recursion tree is roughly // proportional to target/min(candidate). For each recursive call, the algorithm can make up to // n further recursive calls, where n is the number of elements in the candidates array.
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]
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]
Code can be slightly improved by sorting the array and using a checker to only recurse the right subtree if the checker is true/false. So there is no need to see th right subtree if the answer is found in the left subtree since if smaller value gave you the answer, larger will never give you the same answer
TIME ⏰COMPLEXITY EXPLANATION: Let , b = minimum of candidates value. T = given target value. k = average number of elements present in particular answer. t = T / b 't' here is the maximum number of calls (upper bound) needed to make given target (T) -> 0. and in each of the 't' calls we have two choices [pick, unpick] thus, we can write 2 ^ (t) and at last we can multiply it with k, which is self explanatory. I hope this explanation is clear.
can somebody help me please , while tracking we add value inside data structure and decrease value of target , but while backtracking we only remove value from data structure but why don't we add value back to target ?
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 🌟🌟
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.
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.
For those who are wondering why are removing element from ds after the recursive call, it's because ds is getting passed by reference. So if you don't remove the element after push_back() it will stay in the ds for the next recursion calls too. You can verfiy this by yourself. Print the elements of the ds after recursion calls. You will see the last element will be present in the ds if you don't pop it from the array.
can you explain in my code , Where am I making mistake over here since I am not getting and voluntarily I am changing elements in temp in each call void combinSum(vector&arr, int target, int sum,int index, vectortemp, vector&ans){
@@musaveermanekia4035 It is because of the first '2' that you inseted into the temp. The initial (first) '2' cannot be removed from "temp" anyhow, the way you have written the code. And because of that '2' the pair [3,5] can't take place as the two makes it [2,3,5]=10>target.
For those searching through the comments for a python based solution: def soln(arr,k,n,idx,comb_list,arr2 = []): ## BASE CASES START ## if idx == n: if k == 0: comb_list.append(arr2.copy()) return ## BASE CASES END ##
#PICK CASE if arr[idx] List[List[int]]: comb_list = [] soln(candidates, target,len(candidates),0,comb_list) return comb_list
original = [2,3,6,7] target = 7 answer = [] def f(i, target, arr): if i == len(original): if target == 0: answer.append(arr.copy()) return if original[i]
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
so guys if your code is not working for the negative elements.. try removing the 2nd if statement and just run the code..will definitely work..don't thank me just pray for my placement
Why do we only check if target ==0 when index== 'n'? ex; [2,3,6,7] target =6 Here I could arrive at solution by picking 0th element 3 times [2,2,2] so sum equals target. That would not be possible based on your logic because obviously index would be at 0. Visually in rec. tree, this answer resides in left most branch.
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]
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?
What if the value of any array element is zero, in that case, the pick case will keep going on and neither the target will be reached nor the sum or element will ever surpass the target. It will lead to infinite number of recursive calls in the function call stack and eventually segmentation fault.
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..
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.
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
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
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.
You are awesome! Feeling confident in recursion now. Thanks a million!
Legend is back, with another mind-boggling video🔥
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
best explanation on youtube
Thankyou for the lovely content
Striver bhaiya has an another level of explanation. Understood every single words and entire approach🔥💥
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!! ❤️❤️❤️❤️🙌🙌🙌
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.
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...
Striver thank you very much bro 😊
All is clear. One moment: 13:00 🕐 it is valid base case if targer < nums[i] -> return
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 ?
This is the same as of unbounded knapsack along with printing all psbl combinations.
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
amazing striver only beacuse of you i have solve back to back 4 problem of recursion by own thanks a lot
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
grateful to u for providing an easy to understand solution.
this video was the best in whole recursion series like literally you explained the recursion tree so good
Hey Striver, Your videos help a lot. I search for a problem name and add TUF in the front. If you have solved the problem even before video starts I'm happy. As I know if you have explained it I am going to understand it super well. Thank you so much for making these videos
Shandaar Solution bataya sir maja aa gaya,aise hi aasani se samzhate rahiye,thankyou very much
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).
// Time: O(n ^ target/min(candidate))
// The same candidate can be used multiple times in the same combination, meaning the algorithm
// can go deeper in recursion for each element. The depth of the recursion tree is roughly
// proportional to target/min(candidate). For each recursive call, the algorithm can make up to
// n further recursive calls, where n is the number of elements in the candidates array.
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 :(
Code can be slightly improved by sorting the array and using a checker to only recurse the right subtree if the checker is true/false. So there is no need to see th right subtree if the answer is found in the left subtree since if smaller value gave you the answer, larger will never give you the same answer
Hats off to you bhaiya
Best explanation on Recursion .......we can feel what is happening not just learn the pattern of codes in mind
Bro I searched for good videos on backtracking the entire day only to come back to these reliable videos! Very well explained, thank you!
Best possible explanation for this problem ever!!!
Seriously best explanation for back tracking, Genius!
TIME ⏰COMPLEXITY EXPLANATION:
Let ,
b = minimum of candidates value.
T = given target value.
k = average number of elements present in particular answer.
t = T / b
't' here is the maximum number of calls (upper bound) needed to make given target (T) -> 0.
and in each of the 't' calls we have two choices [pick, unpick]
thus, we can write
2 ^ (t)
and at last we can multiply it with k, which is self explanatory.
I hope this explanation is clear.
can somebody help me please , while tracking we add value inside data structure and decrease value of target , but while backtracking we only remove value from data structure but why don't we add value back to target ?
@@suyashshukla6657 as target is passed by value not reference......
thank you so muchhhh!!!
Great explanation bhaiya,, love the way u teach❤💯
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 🌟🌟
thanks bhaiya for amazing content
Bhaiya!!!❤️❤️❤️❤️
OP explanation!!🙏🏽🙏🏽
your method is just amazing to get the understanding
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 .
First time i could understand how it is working
wow, what a detailed explaination. Amazing
after watching your subsequent video i was able to solve this by my own thank you!!
Python solution:
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def backtrack(remain, comb, start):
if remain < 0:
return
if remain == 0:
res.append(list(comb))
for i in range(start, len(candidates)):
comb.append(candidates[i])
backtrack(remain-candidates[i],comb, i)
comb.pop()
res = []
backtrack(target, [], 0)
return res
very nice and detailed explanation ! thank you striver 😇🥰
Very nice and clear cut explanation
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.
awesome man...easy to understand..thanx
Thank You So Much Striver Brother...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Really Raj you did explain very very well
void generateCOMBI(int ind,vector &a,vector &ds,vector &ans,int target)
{
if(ind>=a.size())
{
if(target==0)
{
ans.push_back(ds);
}
return;
}
if(a[ind]
For those who are wondering why are removing element from ds after the recursive call, it's because ds is getting passed by reference. So if you don't remove the element after push_back() it will stay in the ds for the next recursion calls too.
You can verfiy this by yourself. Print the elements of the ds after recursion calls. You will see the last element will be present in the ds if you don't pop it from the array.
can you explain in my code , Where am I making mistake over here since I am not getting
and voluntarily I am changing elements in temp in each call
void combinSum(vector&arr, int target, int sum,int index, vectortemp, vector&ans){
for(int i = 0; i < temp.size(); i++){
cout
@@musaveermanekia4035 It is because of the first '2' that you inseted into the temp. The initial (first) '2' cannot be removed from "temp" anyhow, the way you have written the code. And because of that '2' the pair [3,5] can't take place as the two makes it [2,3,5]=10>target.
@@Raju_Sharma852 Thank You I got it , So it's better to not change the temp on every call rather pop back when not need those elements
Can we remove reference then, and remove pop_back()
For those searching through the comments for a python based solution:
def soln(arr,k,n,idx,comb_list,arr2 = []):
## BASE CASES START ##
if idx == n:
if k == 0:
comb_list.append(arr2.copy())
return
## BASE CASES END ##
#PICK CASE
if arr[idx] List[List[int]]:
comb_list = []
soln(candidates, target,len(candidates),0,comb_list)
return comb_list
Thanks bhaiya for Providing this wonderful resource continue this good work for the people who need it
class Solution {
public:
vector subseq;
void helper(vector candidates,int target,vector ds,int idx)
{
if(candidates.size() == idx)
{
if(target == 0)
subseq.push_back(ds);
return;
}
if(candidates[idx]
original = [2,3,6,7]
target = 7
answer = []
def f(i, target, arr):
if i == len(original):
if target == 0:
answer.append(arr.copy())
return
if original[i]
nice bro really good and appericiated😅
*more brief code*
class Solution {
private:
void print( int index , int target , vector &ans , vector temp , vector candidates)
{
if( target= candidates.size())
{
if(target == 0)
{
ans.push_back(temp);
}
return ;
}
temp.push_back(candidates[index]);
// if(candidates[index]
best explaination found on whole youtube
Tough questions feels easy after watching your video
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
Like OMG this series is op
The time complexity should be (2^nt)*k
yeah
understood, thanks for the perfect explanation
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
so guys if your code is not working for the negative elements.. try removing the 2nd if statement and just run the code..will definitely work..don't thank me just pray for my placement
Hi Striver. Your content is super amazing. Can you please make a backtracking solution video on Gray Code question of LeetCode?
C++ code: 26:09
Thank you bhaiya for this wonderful explaination 😄 Now recursion is crystal clear.
Why do we only check if target ==0 when index== 'n'?
ex; [2,3,6,7] target =6
Here I could arrive at solution by picking 0th element 3 times [2,2,2] so sum equals target. That would not be possible based on your logic because
obviously index would be at 0. Visually in rec. tree, this answer resides in left most branch.
i have the same doubt bro
Welcome back raj bhiya 🥳
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
Something going wrong on UA-cam
In many videos it's showing no views
But likes are more than 1K+
Just like this video....
alag he level k explanation hai bhai k
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?
You are a life saver. Can't thank you enough.
Amazing Explanation..Thanks Striver!!!
Why to check till index==length? We can return if the target reaches zero or in the second condition if the trarget
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?
Thank You so Much Sir
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 :)
What if the value of any array element is zero, in that case, the pick case will keep going on and neither the target will be reached nor the sum or element will ever surpass the target. It will lead to infinite number of recursive calls in the function call stack and eventually segmentation fault.
I love your way of explaining .Really love u man .
can also sort array before calling function:: reduces useless calls
you are great my brother... I am really falling in love with your style ❤.
Understood ✅ #Grateful
I was able to solve the problem for the first time without any help..thanks striver
I have used the loop and single recursion call
Thanks a lot, bhaiya. ❤
How it gonna work if the given array of integers (candidates) also contains negative values and the target sum = 0?
masterpiece ❤️🤗
Thank you striver bhaiya for such amazing explanations.
Wow explanation, literally mind blowing!
thanks bhaiya all my doubts got cleared in this video great content keep educating us 😀👍🏽
Bro can u explain me the time complexity?
Understood Bhaiya!!
Thanks alot
You deserve a Bharat Ratna, Mr. Raj Vikramaditya.
Thank You Striver💖💖