Table of Contents: (I'm sorry, I messed up the audio and am talking pretty loud) Problem Introduction 0:00 - 1:57 The "3 Keys To Backtracking" 1:57 - 4:55 The FULL Recursion Walkthrough For "boat" 4:55 - 22:57 Time & Space Complexities 22:57 - 27:53 Wrap Up / Conclusion 27:53 - 28:18 This is super long because of the walkthrough...I'm sorry. Here is a good example of the code: javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html (If this link doesn't work then you can find the code anywhere, just know the concepts and you can implement it however you want, but I really should have walked through that code snippet. I will try to this in a later video, this is my fault.)
It does alright. The growth rate is good. It can be faster and we haven't gone on to create "viral" content. Since November I've been mostly coding and not focused on growing the channel. Between December 2018 and November 2019 I only made niche programming question videos and they operate like a library. A library is stable and grows slowly. The channel still operates like a library and not an active mechanism of rich media generation. If we made media that could scale to capture more people (less technical, talk about salaries or something which is a hot, attractive topic) we would grow exponentially. I am well aware where we stand and what the TH-cam is as well as where it can go. Entities on the internet can deserve things, but attention distribution is not fair and follows the pattern of natural selection with a great bit of unfairness.
@@BackToBackSWE I love the content on this channel. Do you know what makes this channel different from the rest? You guide us through the approach and you don't explain the code. After watching the video I can code in like 5 minutes and I will never forget the solution. Thank you so much for all the videos and keep making quality voices. 🙂
11:51 "I feel like a robot right now" :) But you are not a robot, so it is exhausting for a human being to do this. It's amazing how much simpler the actual code is than doing it manually yourself. It is one of the most powerful examples of why computers are useful. Despite all that, I *really* appreciate you putting yourself through that on video because it fully and completely demonstrates the intuition behind the code.
I've never had so much fun watching an educational video, the backtracking steps explanation is so great Love your attitude, your persnoality and you explain things so well Great Video
Man, great job with that explanation on the whiteboard. Having a mental model for this problem is hard enough, but explaining each step and having to make all those edits into a video must've been really tough. Thanks for your hard work!
You are just so good at explaining those sort of ideas! The beauty of is I don't have to finish the video to get your idea. I stopped the video at 5 minutes and able to go back and resolve my problem.
Time complexity for that proposed "and now"-count Algorithm is the same as this permutations Algorithm.... also kidding of course, this is a good tutorial
"exhausted all possibilities of x, no more backtrack"!!. Love your effort man, really. I finally understood backtracking! Yeah, I needed explanations 24 times! thank you :)
dude...keep it up! I could care less about the negative comments, ignore them. As a very seasoned software engineer, company founder, and exceptional teacher, I can safely say you have described this in the most laymen way possible. Excellent! Would love to connect with you and discuss a couple of things. Reach out to me on linkedin
This video is old haha, are the comments bad? I don't notice. I just respond to the stream that hits my notification bell. I don't use LinkedIn much, maybe email me? backtobackswe.com/contact
ha ha! The artistic license with backtracking in the video is cute. The jumpiness of the video get's a little much. However, overall, the language used is clear and that makes understanding the approach easily understood ! Well done!
Amazing explanation very clear! I did a masters (1 year conversion course) in Computer Science and they never even mentioned the concept of backtracking so this is very helpful thanks.
Wow dude i had seen lot of tutorial but yours its the most amazing , clear and comprehensive ,thanks for take the time to do this , im subscribed now , greetings
There's a difference between understanding something and being able to make others understand the concept. Great job ! I Understood the concept of backtracking to a great extent.
Good video. Learned the theory. It would have been nice to SEE the code and discuss tradeoffs of the different ways of programming the backtrack algorithm which is what I wanted but I like how you mentioned some of those ways.
This is awesome. I totally understand it better than before. I am having a hard time putting this into recursion though. do you mind making the code live again?
Suggestion: Try to stand on the opposite of the board you are writing. It's tough sometimes to take notes when you are standing directly in front of what you wrote out. Great job otherwise.
how is space complexity O(n*n!) when we store in an array. we are storing the result so it should take O(n!). can you please explain. Thanks for the explanation.
I'm wondering if the time complexity is calculated as the total number of function calls, it would be exactly the number of nodes been traversed in the "tree." So that would be counted in such manner(from top of the tree, each term represents the number of nodes on each layer): N + N(N-1) + N(N-1)(N-2) … + N(N-1)(N-2)…(3) + N(N-1)(N-2)…(2) + N!, and this gets to e*N! as N gets large. Please correct me if I'm wrong. Thanks!
For time complexity, can you please explain beyond the fact that there are n! permutations that need to be computed? I think the number of recursion calls is more than that, but not sure how to formally count this (also not sure if interviews will ask for that level of mathematical formalism)
The recurrence for generating permutations recursively is: T(n) = n * T(n-1) + O(1) where we just print the permutation (we don't copy a string to an answer list or anything). In each call, we will make n calls and n will reduce in size by 1. Each call will do at worst O(1) work. If n = 4 then we will see it concretely solves to n * (n - 1) * (n-2) * (n-3) where T(1) is a base case entailing a print. Does this make sense?
If we used a StringBuilder instead of a Strings would the time efficiency be O(n!) and not O(n *n!)? I think that with StringBuilder we can just append the 'choice' in each frame instead of deep copying the String?
thank you sir for great job. : ) plz make tutorial on the case when reapting char are there in string without reapting permutation like "Boom". it printed twice. how to avoid this reaptation without using "HashMap" and "Set".
We could just put the permutations in a HashSet but then again there is probably a smarter way to prune the placements going downwards. Reminds me of: leetcode.com/problems/subsets-ii/ I'll think on this.
Great explanation, thank you so much! I have a question about the space complexity when we just print our permutations. The worst case is when we reach the bottom of our recursion and that would be O(n) because of n stack frames, I get it. But every stack frame also has its current state, I mean current permutation, which is also of length n in worst case. Am I right? Shouldn't space complexity in this case be O(n*n) = O(n^2)? Thanks a lot!
Yes, that would be the case, but if you pass a reference to a single mutable string (maybe make your own char array) you can keep the space linear (no copies in each frame of a whole structure).
So our original string will be "boat" . I immediately know that in the 1st slot the "b" will go first with a remainder of "oat", then the "o" with a remainder of "bat", then the "a" with a remainder of "bot", then the "t" with a remainder of "boa". That is what the first positioning will yield. So...4! = 24. We know that we will have 24 total permutations (for reasons I think this video explains...I did this a while back so not sure). So go back to what I was saying...."b" will go first with a remainder of "oat". With "b" in slot 1 (and 3 remaining slots)...I know for sure that I will be able to reap 6 permutations. Why? Well...3! = 6. So ok....we know that the 7th permutation will start with the "o" placed in the first slot with a remainder of "bat". So from there we can just do the enumeration and get there faster... We hopped to the 7th...and that is: o b a t _ _ _ _ If you followed this whole explanation then you should have a deeper understanding of what is happening.
what was 6.9? I don't have the book up with me rn. I had to wipe my hard drive (had issues) and I'm setting shit back up again now...so yeah...I assume it is the same problem using an array? A string is an abstraction, it is an array of characters. It is a sequence. Any sequence can be permuted.
Back To Back SWE it’s okay and thanks for your attention...the problem of chapter 6 number 9 is Give an array A of n elements and a permutation p, apply p on A.. this part is easy to implement but the point is he said in the book any permutation can be viewed as a set of cyclic permutations for each element in the cycle how’d you identify if it has been permuted ..I didn’t understand what does it mean
@@abdelrahman2348 OHHHH, just pulled it up. Not it is not the same. And yeah, I just read the "Hint: Any permutation can be viewed as a set of cyclic permutations. For an element in a cycle, how would you identify if it has been permuted?" For this problem they say "A permutation can be specified by an array P". This is different from what we call a permutation in this problem. A permutation in that context is the codification of final positions for items. The "Hint" is that each permutation represents a series of interlinked steps to get all elements to their final positions so that O(1) space can be used (since it is trivial to perform the repositionings into a new array). These interlinked swaps form a series of "cycles" where we must swap an element in...then swap the element that sat where we just swappped into its final place...and so on... That is an odd way of saying it but yeah...that's the gist of it.
Sad that you are also like other TH-camrs as you are also solving the problem not explaining the code. I think code explanation is much much better but sadly I have to pay everywhere to get the code explanation.
@@BackToBackSWE Firstly thanks for replying and Yes people should charge for there work as they are spending a lot of time and effort but from a student point of view there are so many places to study but only some of them are good (like yours) that students like me got confused how to study and where to pay the charges as in starting everything works fine but at the end, it's all messed up and being a student its hard to pay everywhere to get the materials and learn. But you are doing a great job. Big thumbs up for you. 👍😁
![[UNCUT] The Loyal Pin ปิ่นภักดิ์ EP.15 (3/4)](http://i.ytimg.com/vi/IVwR87OH0_A/mqdefault.jpg)
Table of Contents: (I'm sorry, I messed up the audio and am talking pretty loud)
Problem Introduction 0:00 - 1:57
The "3 Keys To Backtracking" 1:57 - 4:55
The FULL Recursion Walkthrough For "boat" 4:55 - 22:57
Time & Space Complexities 22:57 - 27:53
Wrap Up / Conclusion 27:53 - 28:18
This is super long because of the walkthrough...I'm sorry.
Here is a good example of the code: javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html
(If this link doesn't work then you can find the code anywhere, just know the concepts and you can implement it however you want, but I really should have walked through that code snippet. I will try to this in a later video, this is my fault.)
pro trick: you can watch series at flixzone. Me and my gf have been using them for watching lots of of movies lately.
@Jase Harold Yea, been using flixzone} for since december myself =)
He is one of the few people on TH-cam who actually elaborate the concept of backtrack clearly. Great job!
Who else feels that this channel deserves more subscribers?
It does alright. The growth rate is good. It can be faster and we haven't gone on to create "viral" content. Since November I've been mostly coding and not focused on growing the channel.
Between December 2018 and November 2019 I only made niche programming question videos and they operate like a library. A library is stable and grows slowly.
The channel still operates like a library and not an active mechanism of rich media generation. If we made media that could scale to capture more people (less technical, talk about salaries or something which is a hot, attractive topic) we would grow exponentially.
I am well aware where we stand and what the TH-cam is as well as where it can go. Entities on the internet can deserve things, but attention distribution is not fair and follows the pattern of natural selection with a great bit of unfairness.
@@BackToBackSWE I love the content on this channel. Do you know what makes this channel different from the rest? You guide us through the approach and you don't explain the code. After watching the video I can code in like 5 minutes and I will never forget the solution. Thank you so much for all the videos and keep making quality voices. 🙂
Also I think so @Sushmita S Nataraj
I want to get "No More Decisions To Make Backtrack" tattooed on my arm after this.
hahaha same
11:51 "I feel like a robot right now" :) But you are not a robot, so it is exhausting for a human being to do this. It's amazing how much simpler the actual code is than doing it manually yourself. It is one of the most powerful examples of why computers are useful. Despite all that, I *really* appreciate you putting yourself through that on video because it fully and completely demonstrates the intuition behind the code.
sure thx
I've never had so much fun watching an educational video, the backtracking steps explanation is so great
Love your attitude, your persnoality and you explain things so well
Great Video
thx
Man, great job with that explanation on the whiteboard. Having a mental model for this problem is hard enough, but explaining each step and having to make all those edits into a video must've been really tough. Thanks for your hard work!
nice - thx
outstanding job dude. Over a year and i still go back to this
You are just so good at explaining those sort of ideas! The beauty of is I don't have to finish the video to get your idea. I stopped the video at 5 minutes and able to go back and resolve my problem.
great to hear!
love the ENERGY my guy - earned a sub
thx
Not the teacher we deserve, but the teacher we need..hats off !!!
thanks haha
Love ur energy n enthusiasm to get to depth of a problem rather than just solving the problems...
Good job!
sure
Write a code to count number of “now”s in this video! 😂
Just kidding, good tutorial
I say that a lot. Weird mannerism. I can't control them....well I could consciously try...eh...whatever
Time complexity for that proposed "and now"-count Algorithm is the same as this permutations Algorithm.... also kidding of course, this is a good tutorial
"exhausted all possibilities of x, no more backtrack"!!. Love your effort man, really. I finally understood backtracking! Yeah, I needed explanations 24 times! thank you :)
Generally i don't comment, but dude this explanation is exceptional.I never understood string permutations this better. great work
welcome to commenting lol & thx
best lecture for this question on the entire TH-cam
Appreciate the enthusiasm to explain all the 24 combos !!
dude...keep it up! I could care less about the negative comments, ignore them. As a very seasoned software engineer, company founder, and exceptional teacher, I can safely say you have described this in the most laymen way possible. Excellent! Would love to connect with you and discuss a couple of things. Reach out to me on linkedin
This video is old haha, are the comments bad? I don't notice. I just respond to the stream that hits my notification bell. I don't use LinkedIn much, maybe email me? backtobackswe.com/contact
You're addictive to watch, incredibly entertaining, and amazingly informative. Thanks!!
thank you. means a lot. Would love some feedback on the free 5 day course - backtobackswe.com/
You are great!!! 1 important thing - please put links to the previous videos of yours that you are referring to. It would really help. thanks!!
ha ha! The artistic license with backtracking in the video is cute. The jumpiness of the video get's a little much. However, overall, the language used is clear and that makes understanding the approach easily understood ! Well done!
"The artistic license with backtracking in the video is cute." what
and yeah sorry old video. and nice, surprising this one was rough, and thanks
This must have been exhausting to film.
Thanks for that. I would like to see a code walkthrough next.
sure
Jeez, I thought he is going to write a code :(
Here Is My Response: backtobackswe.com/im-sorry
Github: github.com/bephrem1/backtobackswe/issues/1
you are awesome, I watch a lot of your videos for help!
One of the best tutorials I have ever seen. Great job
Thanks
huge respect for such massive amount of efforts exerted. very much appreciate them! for a beginner in recursion, very very helpful.
sure
Amazing explanation very clear! I did a masters (1 year conversion course) in Computer Science and they never even mentioned the concept of backtracking so this is very helpful thanks.
sure
Yoo.Thanks my man.This was really helpful.
Amazing explanation, I have a interview coming up and i will keep this in mind for any permutation problem!
love
I really enjoy learning from you, thank you for posting this.
Wow dude i had seen lot of tutorial but yours its the most amazing , clear and comprehensive ,thanks for take the time to do this , im subscribed now , greetings
There's a difference between understanding something and being able to make others understand the concept. Great job ! I Understood the concept of backtracking to a great extent.
great
never seen this much energy ! thanks dude
I'm a wild guy
The code was tricky to wrap my head around. This helped very much, thank you!
Take a bow.......my brother
what an effort
ye
I like how passionate you are about teaching ^^
thank you very much for the video !!
Very attractive teaching style.good job sir
thanks
You are my Prof.
Thanks for the awesome vid! Voted!
sure
this is dope you're doing a great job, keep it up
a lot of work ahead this year
When recursion makes that gym membership pay off 😂 Great explanation. Thanks
wut
Good video. Learned the theory. It would have been nice to SEE the code and discuss tradeoffs of the different ways of programming the backtrack algorithm which is what I wanted but I like how you mentioned some of those ways.
Yeah. I realized this after I did it.
Check this out: github.com/bephrem1/backtobackswe/issues/1
I will give this code and maybe do another video.
Great job man, you are really good at explaining
thanks!
Thanks sir, first 4 minutes and got the idea how to solve it.
nice
exactly same here ....!
watched the video till 4:07 mins
@@shubhamjindal9214 haha nice
Amazing video!
You're really helping me to crack the coding interviews!
I just wanna say, great job.
thx
Watching this at 0.75 speed seems pretty good. :)
thx sorry old vide
Great explanation bro hats off for your patience
ok
Love the energy !
This is awesome. I totally understand it better than before. I am having a hard time putting this into recursion though. do you mind making the code live again?
Thanks and the repository is deprecated - we only maintain backtobackswe.com now.
wow thank you for such a great video!
"No more decisions to make, backtrack" - this one was nice though.. :P
thanks
You are awesome!!
thx
Suggestion: Try to stand on the opposite of the board you are writing. It's tough sometimes to take notes when you are standing directly in front of what you wrote out. Great job otherwise.
ok
A big thank you 😊
sure
Nice Explanation. Thank you.
sure
Great job! so for array permutation problem, the time complexity should O(n!), space complexity is O(n), n is the size of input array.
Which version?
GREAT !!!
I liked your lectures !
thanks
7:55 felt like watching Edge Of Tomorrow. LOL! But its great !!
how is space complexity O(n*n!) when we store in an array. we are storing the result so it should take O(n!). can you please explain. Thanks for the explanation.
I don't remember this to be honest
Well, I guess n! is for the permutation purpose and n to print each permutation so that makes it O(n*n!). Not sure!!
@@namanmishra3778 Yea Whatever you are saying is for time complexity. but my doubt is about space complexity dude
I'm wondering if the time complexity is calculated as the total number of function calls, it would be exactly the number of nodes been traversed in the "tree."
So that would be counted in such manner(from top of the tree, each term represents the number of nodes on each layer): N + N(N-1) + N(N-1)(N-2) … + N(N-1)(N-2)…(3) + N(N-1)(N-2)…(2) + N!, and this gets to e*N! as N gets large. Please correct me if I'm wrong. Thanks!
I'm not fully clear on the format of what you are summing
@@BackToBackSWE
this might be clear
imgur.com/a/dkUb8V1
Is there any alt of recursion. Seriously this recursion is killing me...😢😢
what if the string length is 50 or something. Is there any way to calculate all the permutations in an efficient way for that case ?
I'm not sure
For time complexity, can you please explain beyond the fact that there are n! permutations that need to be computed? I think the number of recursion calls is more than that, but not sure how to formally count this (also not sure if interviews will ask for that level of mathematical formalism)
The recurrence for generating permutations recursively is: T(n) = n * T(n-1) + O(1) where we just print the permutation (we don't copy a string to an answer list or anything). In each call, we will make n calls and n will reduce in size by 1. Each call will do at worst O(1) work. If n = 4 then we will see it concretely solves to n * (n - 1) * (n-2) * (n-3) where T(1) is a base case entailing a print. Does this make sense?
Good job Bro!
thx
Definitely can't say 'do you even lift bro?' to this guy
If we used a StringBuilder instead of a Strings would the time efficiency be O(n!) and not O(n *n!)? I think that with StringBuilder we can just append the 'choice' in each frame instead of deep copying the String?
Im not sure I dont remember
Can you provide the code? I could not find the link.
yeah, it's been open on the github for a while as an issue
woahh....great energy man!!
old video - sorry
Thanks bro really helpfull
Sure
Every time I listen your video I think need to set playback speed to 0.75%
sorry - old video i understand
Is your old github repo with the solutions still available or is that behind Backtobackswe.com now?
At 11:00 I definitely could feel the mental struggle
Very Clear explanation , Thanks a lot bro . Looking for more DP videos .
sure
you're DS god 🙏🙏🙏 love from India ❤
thank you sir for great job. : )
plz make tutorial
on
the case when reapting char are there in string
without reapting permutation like "Boom".
it printed twice.
how to avoid this reaptation without using "HashMap" and "Set".
ok
it would be good, if you can explain wrt code
yeah
I like this guy
the question is, how do you transfer your "running string" down the call stack without making a deep copy of it each time? Requires some trickery...
Can we solve this problem without recursion
yes, but I don't remember how its coded. you can probably find a solution online
Didn't know alexandre lacazette was a software engineer
What if there are duplicate elements in the array, how do you avoid generating duplicate array for the answer?
We could just put the permutations in a HashSet but then again there is probably a smarter way to prune the placements going downwards.
Reminds me of: leetcode.com/problems/subsets-ii/
I'll think on this.
what does a naive solution to this look like? without backtracking
As in an iterative approach? How would you brute force generating permutations?
These permutations kind of remind me on generative recursion. Backtracking, I learn is for search? This bothers me sometime now.
ye
thanks !!
sure
Thanks God, that in word `boat` is 4 letter and not 5
yeah
Posting the code for this would be helpful
github.com/bephrem1/backtobackswe/issues/1
;)
man checking abs often:")
wat
If you would have not erased and drawn full recursion tree the understanding would have been better
yes
Great explanation, thank you so much!
I have a question about the space complexity when we just print our permutations.
The worst case is when we reach the bottom of our recursion and that would be O(n) because of n stack frames, I get it. But every stack frame also has its current state, I mean current permutation, which is also of length n in worst case. Am I right? Shouldn't space complexity in this case be O(n*n) = O(n^2)?
Thanks a lot!
Yes, that would be the case, but if you pass a reference to a single mutable string (maybe make your own char array) you can keep the space linear (no copies in each frame of a whole structure).
@@BackToBackSWE Yeah, you're right, thank you!
In your example, how would I figure out that “obat” is the 8th permutation without writing out all possible permutations that came before it?
So our original string will be "boat" . I immediately know that in the 1st slot the "b" will go first with a remainder of "oat", then the "o" with a remainder of "bat", then the "a" with a remainder of "bot", then the "t" with a remainder of "boa".
That is what the first positioning will yield.
So...4! = 24. We know that we will have 24 total permutations (for reasons I think this video explains...I did this a while back so not sure).
So go back to what I was saying...."b" will go first with a remainder of "oat".
With "b" in slot 1 (and 3 remaining slots)...I know for sure that I will be able to reap 6 permutations.
Why? Well...3! = 6. So ok....we know that the 7th permutation will start with the "o" placed in the first slot with a remainder of "bat".
So from there we can just do the enumeration and get there faster...
We hopped to the 7th...and that is:
o b a t
_ _ _ _
If you followed this whole explanation then you should have a deeper understanding of what is happening.
Here's my question. What if there is repeating letter in a string?
I don't remember but these's a way
thanks a lot
sure
super>>
thanks
why boat with 24 permutation , why not cat with 8 permutation, would have made your job easy.......... but hats off to your energy
I don't remember this video too much in detail, old video, bad mic, I was loud
What is the difference between this problem and 6.9 in aziz's book ?
what was 6.9? I don't have the book up with me rn. I had to wipe my hard drive (had issues) and I'm setting shit back up again now...so yeah...I assume it is the same problem using an array?
A string is an abstraction, it is an array of characters. It is a sequence. Any sequence can be permuted.
Back To Back SWE it’s okay and thanks for your attention...the problem of chapter 6 number 9 is
Give an array A of n elements and a permutation p, apply p on A.. this part is easy to implement but the point is he said in the book any permutation can be viewed as a set of cyclic permutations for each element in the cycle how’d you identify if it has been permuted ..I didn’t understand what does it mean
@@abdelrahman2348 OHHHH, just pulled it up. Not it is not the same. And yeah, I just read the "Hint: Any permutation can be viewed as a set of cyclic permutations. For an element in a cycle,
how would you identify if it has been permuted?"
For this problem they say "A permutation can be specified by an array P". This is different from what we call a permutation in this problem. A permutation in that context is the codification of final positions for items.
The "Hint" is that each permutation represents a series of interlinked steps to get all elements to their final positions so that O(1) space can be used (since it is trivial to perform the repositionings into a new array).
These interlinked swaps form a series of "cycles" where we must swap an element in...then swap the element that sat where we just swappped into its final place...and so on...
That is an odd way of saying it but yeah...that's the gist of it.
@@BackToBackSWE Thank you, but I still can't figure out it the permutation cycle , could you discuss it later in a video ?
@@abdelrahman2348 possibly
Man there's some problem with this video. It just gets stuck buffering after first 20 seconds.
hm
Seriously Man 😵
@@ezpz4akash yuh
while writing the code you are looping over l to r but in helper fuction u will pass l+1 not i+1 like your rest of the backtracking videos.
where?
@@BackToBackSWE void util(vector &A,vector &v,vector &sub,int data){
// if(data==A.size()){
v.push_back(sub);
for(int i=data;i
but, in case of string permutation
void permute(string a, int l, int r)
{
// Base case
if (l == r)
cout
superb 🔥🔥🔥🔥🔥🔥🔥🔥
thx
Sad that you are also like other TH-camrs as you are also solving the problem not explaining the code. I think code explanation is much much better but sadly I have to pay everywhere to get the code explanation.
I explain this in other videos and yeah people charge for (a minority share of) their work shocker
@@BackToBackSWE Firstly thanks for replying and Yes people should charge for there work as they are spending a lot of time and effort but from a student point of view there are so many places to study but only some of them are good (like yours) that students like me got confused how to study and where to pay the charges as in starting everything works fine but at the end, it's all messed up and being a student its hard to pay everywhere to get the materials and learn.
But you are doing a great job. Big thumbs up for you. 👍😁