Great explanation! Thank you! Could you please prepare a general video to explain how to set-up a DFS parameters and its stop condition (Many LeetCode problems similar to this but always the toughest thing is to identify what parameters are needed for the DFS)
@Cracking FAANG Thanks for an AMAZING video. It's super concise and easy to understand. It's been an year but wanted to make a comment on this as I was thinking thru the complexities in the end. I am not too convinced that the Space Complexity is actually O(N), I think it should be at least O(3^N) similar to Time Complexity. I say this because I think the space needed doesn't grow linear with additional input, but rather exponentially to the additional input. Would love to know your thought on this. Thanks
Damn.. what a solution!! I was thinking of generating all expressions using recursive backtracking (by inserting operators into num at alternate places), then using the eval() function in python, evaluate the string expression and see if eval(''.join(exp)) == target, append only those exp to res. Sadly, this approach was giving a TLE 🥲 Great solution btw!
Thanks for the detailed explanation!! I've a query, are we using cur_res as a list instead of a string because strings are immutable and addition of a character to a string takes O(N)?
because when something like this happends `1-2*3*2` you need that must be the same as `1-(x*y)` at before the `-`. If you step through the code on `1-2*3*2` it will make sense. That's what i did.
void rec(int cur_idx, string cur_res, long long cur_sum, long long prev, string &num, int target){ if(cur_idx>=num.size()){ if(cur_sum==target){ ans.push_back(cur_res); } return; }
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Great explanation! Thank you!
Could you please prepare a general video to explain how to set-up a DFS parameters and its stop condition (Many LeetCode problems similar to this but always the toughest thing is to identify what parameters are needed for the DFS)
Awesome! Thank you, we missed you!
@Cracking FAANG Thanks for an AMAZING video. It's super concise and easy to understand.
It's been an year but wanted to make a comment on this as I was thinking thru the complexities in the end.
I am not too convinced that the Space Complexity is actually O(N), I think it should be at least O(3^N) similar to Time Complexity.
I say this because I think the space needed doesn't grow linear with additional input, but rather exponentially to the additional input.
Would love to know your thought on this. Thanks
Damn.. what a solution!! I was thinking of generating all expressions using recursive backtracking (by inserting operators into num at alternate places), then using the eval() function in python, evaluate the string expression and see if eval(''.join(exp)) == target, append only those exp to res.
Sadly, this approach was giving a TLE 🥲
Great solution btw!
this was my exact solution, and then I got TLE
Welcome back. Thanks for the cool explanation...
Nice video. I liked the video. Would like to request “Nested List Weight Sum II”. You solve the first version 4 month ago but not the 2nd one
Thanks for the detailed explanation!! I've a query, are we using cur_res as a list instead of a string because strings are immutable and addition of a character to a string takes O(N)?
how is space not also 4^n, cant we create that many stack frames of dfs in the worst case
Amazing explanation!
Do you have any link where you post your solutions so we can use it to run through it line by line?
I don't currently have a github for the solution code but I really should set one up
good explaination!
Thanks. Very well explained :)
Awesome!!
Glad you found it helpful! Subscribe if you haven’t already 😃
wooooowwwwwww
can you explain why in multiplication part of the dfs prev becomes curr_num*prev?
because when something like this happends `1-2*3*2` you need that must be the same as `1-(x*y)` at before the `-`. If you step through the code on `1-2*3*2` it will make sense. That's what i did.
@@lesterdelacruz5088 hey thanks for the explanation
Great video could you please do Valid Palindrome III LC 1216.
why not eval at end?
why break when cur_idx is at 0?
nevermind got it!
come back G, shit ain't the same without you
Comeback is planned… sometime later this month 👀
@@crackfaang hell yea!!! prepping for Meta with your videos atm
@@roywastaken same lol. Gotta do those 172 for last 6 mo
Sick ty
can anyone help me with the c++ code?
class Solution {
public:
vector ans;
void rec(int cur_idx, string cur_res, long long cur_sum, long long prev, string &num, int target){
if(cur_idx>=num.size()){
if(cur_sum==target){
ans.push_back(cur_res);
}
return;
}
string cur_str = "";
for(int j=cur_idx;j