Hi Greg, I could not understand how the pop is working here, once we have the first solution, I dont understand how pop is happening twice in the for loop.
Hello Saurabh, Here is how pop() does the work here.After we append the first solution to ans,the control gets back to the "sol.pop()"line and we pop 3 from sol since its the last element. At this stage note that we are in the last iteration of for loop as well since x =3. So we don't have to execute anything further with backtrack() when x=3. So now we return back the sol which is [1,2] to backtrack() when x =2. Now the next line is sol.pop().So we pop 2 from sol and hence sol becomes [1].but here is the catch... now x=2 and the loop has 1 more interation for x=3 so we check if 3 is in solution and add it into sol and sol becomes [1,3], now we call backtrack() and we compare the len of sol to n which is not equal to 3 so we start the for loop afresh once again and check if 1 is in sol. Yes 1 is in sol=[1,3],but in next iteration when x=2 since 2 is not in sol, we add it to sol and add it to ans. This is how we formulate the 2nd solution. Hope you can figure out the flow for remaining solutions and hope this helped😊
I think this problem is purely a test of how to code it concisely. Leetcoding to land a Meta/Google position. Gotta use code that interviewers can read... so found 3 solutions: Dupes Insertion into a growing temp linkedList Rotations Took me a couple hours to solve on my own, giving up, then looking it up.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Greg you have natural talent in teaching, kindly don’t stop making videos
Awe that's so sweet. Probably just practice as I've been learning and teaching for awhile now. I really appreciate it!! 😊
so much better than neetcode
have to agree on that one
Yeah
such an elegant explanation. Thanks Greg!
Hi Greg, I could not understand how the pop is working here, once we have the first solution, I dont understand how pop is happening twice in the for loop.
Leaving a comment here as I want to also know
Hello Saurabh,
Here is how pop() does the work here.After we append the first solution to ans,the control gets back to the "sol.pop()"line and we pop 3 from sol since its the last element. At this stage note that we are in the last iteration of for loop as well since x =3. So we don't have to execute anything further with backtrack() when x=3. So now we return back the sol which is [1,2] to backtrack() when x =2. Now the next line is sol.pop().So we pop 2 from sol and hence sol becomes [1].but here is the catch... now x=2 and the loop has 1 more interation for x=3 so we check if 3 is in solution and add it into sol and sol becomes [1,3], now we call backtrack() and we compare the len of sol to n which is not equal to 3 so we start the for loop afresh once again and check if 1 is in sol. Yes 1 is in sol=[1,3],but in next iteration when x=2 since 2 is not in sol, we add it to sol and add it to ans. This is how we formulate the 2nd solution. Hope you can figure out the flow for remaining solutions and hope this helped😊
This was excellent. Thank you
I think this problem is purely a test of how to code it concisely.
Leetcoding to land a Meta/Google position.
Gotta use code that interviewers can read... so found 3 solutions:
Dupes
Insertion into a growing temp linkedList
Rotations
Took me a couple hours to solve on my own, giving up, then looking it up.
I learned backtracking thanks to you, thanks Greg!
Amazing 😍😍
Beautiful teaching
Thanks a ton!!!
Woow ! You made look so simple . Good job. Keep doing such videos
Thank you!
Isn't the time complexity N! * n? , checking if x in sol is n
or copying solution before you add it is n
Excellent video!
How would the code change if there are duplicate numbers in the array?
Thank you! And there's actually a problem for that, might cover it at some point :)
bro what is if x not in sol, can you explain that I don't understand bro
If we've already used the number, we don't want to use it again
its O(n! * n), because of the line: if x not in sol
Same for the space complexity. It should be O(n! * n)
hell yeah