All possible permutations | Decoding Recursion | Nishant Chahar | Ep-8
All possible permutations | Decoding Recursion | Nishant Chahar | Ep-8
Here in this video, we have solved a problem permutations. Watch it till the end, to understand it completely. Also share it with your friends if you find these lectures helpful.
Permutations Problem link: https://leetcode.com/problems/permuta…
You can use my code NISHANT to get 15% Off on all GFG courses.
✨ Important Links ✨
- Don’t Click Here: https://bit.ly/3afmPha
- Telegram Link: https://t.me/codeIn10byNishant
- Github Repo Link: https://github.com/chaharnishant11/Co…
✨ Hashtags ✨
#NishantChahar #Microsoft #DSA #Recursion #FAANG #NSIT #NSUT #engineering #internship #college
✨tags ✨
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn Operating systems
where to learn dbms
where to learn oops
where to learn computer networks
where to learn low level design
where to learn cs fundamentals
Sanchit jain
Gaurav sen
Gate smashers
Placement guide
How to start programming
where to learn cpp
where to learn python
where to learn javascript
where to learn java
Placement guide
Nishant Chahar Placement Guide
languages to learn
resources to learn data structures
Projects development
AR/VR
Blockchain Machine learning
Deep Learning
Software developer engineer ,
Side projects ,
Importance of side projects ,
Machine Learning Engineer,
How to become a machine learning engineer ,
Associate engineer
Data structures Algorithms
College Life, College, Memories
Fun Fests Chill Enjoy
IITD Mood indigo rendezvous IIT
NSUT Moksha DTU Engifest
Bits Bitsgoa
Namaste Javascript
Namaste Javascript Akshay Saini
Apna college
Apna college c++
apna college DSA
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn programming
how to start coding
where to learn coding
where to learn DSA
resources to learn programming
how to crack amazon
how to crack placement
blockchain
what is blockchain
blockchain technology
blockchain technology explained
blockchain explained
blockchain technology in hindi
web development roadmap
roadmap to learn web development
android development roadmap
MERN stack roadmap
machine learning roadmap
roadmap to learn machine learning
roadmap for deep learning
roadmap for 2nd years
roadmap for opensource
roadmap for ios development
roadmap for deep learning
roadmap to learn DSA
Content
0 -> Hi guys welcome to the channel code in 10 I am Nishant Chahar
2.77 -> So in today's video, we gonna talk about a question whose name is permutations
5.743 -> And first, see what is the scene in it
7.427 -> Given an array of distinct integers
10.858 -> Here distinct is written
12.21 -> Means no number will be repeated again
14.457 -> Okay
15.007 -> Return all the possible permutations
16.821 -> You can return the answer in any order
19.105 -> Means we can return the answer in any order
21.378 -> Now let's take this example
23.037 -> 1,2,3
23.994 -> And let's try playing with it
25.496 -> That what should be its permutations
27.999 -> Now what exactly are permutations
31.1 -> That if we have 3 places
32.92 -> We have 3 elements in 3 places
35.177 -> So in how many ways we can arrange these 3 elements
38.66 -> Okay
39.433 -> So if we have 3 elements, then we can place 3 elements in the first place
42.343 -> At second position we can put two
43.887 -> Because we put one here
45.15 -> And at the last position, we can put only one
46.806 -> So when we will multiply all
48.761 -> So our answer will come out to be 6
50.229 -> And 6 is also 3 factorial
52.428 -> Similarly, if we had 4 elements in it
55.338 -> So what would happen
56.281 -> First, we have 4 to put
59.581 -> Later 3
60.32 -> Then 2
61.094 -> Then 1
61.675 -> So it is 24
63.128 -> This is your 4 factorial
64.673 -> Okay
65.446 -> So we got to understand one thing from it
66.703 -> That whatever is present here
68.498 -> it is n factorial
69.859 -> If we are given number of elements as n
71.551 -> So it will be n factorial. we have studied this in maths
73.631 -> in 11th, 12th
74.593 -> So everyone must know what are permutations
76.401 -> Now how will we do it through code
78.483 -> Let's understand that
79.002 -> Here we have
80.076 -> Like we talked about here
81.353 -> first, we have 3 options
83.605 -> In second we have 2 options
84.331 -> in third , we have 1 option
85.195 -> Let's do the same thing
85.946 -> Okay
86.522 -> In starting, to put in all the three arrays
91.354 -> In first we put 1
93.43 -> In second we put 2
95.196 -> In third we put 3
96.553 -> Okay
97.538 -> So here we will have 2 options to put at second
99.847 -> In all
100.947 -> Because we have put one, one
101.888 -> To put in second we will have 2 options
104.262 -> Here 1 has come
105.541 -> So now 2 can come
106.739 -> here 1 came , now 3 can come
108.333 -> Similarly we will see here
110.064 -> we have got 2
110.968 -> Here 1 can come
111.923 -> here 2 came, here 3 can come
114.17 -> Similarly here 3 came
115.801 -> So 1 can come here
116.526 -> And 3 came ,so 2 can come
119.504 -> Now we are left with one-one option
122.437 -> Right
123.92 -> Now what is that one option
125.568 -> That here 3 is missing so we did this 1,2,3
129.066 -> Here we have 2 missing
131.545 -> So we did 1,3,2
132.673 -> Here 3 is missing
134.254 -> we did 2,1,3
136.751 -> Here 1 is missing
138.142 -> we did 2,3,1
139.519 -> Here 2 is missing
141.005 -> So we did 3,1,2
142.675 -> And in last 1 is missing
144.671 -> So we did 3,2,1
145.824 -> So you will see
148.113 -> We got all the permutations
149.622 -> The total value of them
150.826 -> That became 6
151.895 -> Because this became 3 factorial
154.001 -> This is one way
155.736 -> What we will have to maintain in it
157.141 -> We will have to maintain a count array type
159.942 -> Okay
161.281 -> It is an easy approach
162.736 -> But until you do not know count array and maps
166.369 -> So it can be a little bit complex
168.161 -> That what is this
169.226 -> Why are we doing this
169.991 -> So we will discuss this later
171.794 -> This is very easy
172.71 -> In it , our more space is occupied
175.227 -> Because we are using an extra array
177.959 -> So that is why we feel some trouble
180.674 -> Now there is one more approach for it
182.07 -> A little bit optimized approach
183.701 -> A little bit better approach
184.784 -> That we gonna code today
186.157 -> Okay
186.916 -> And we gonna understand how it works
188.472 -> Now if you see
189.914 -> What exactly is happening here
192.734 -> We are saying
194.092 -> That swap your positions once
196.738 -> And if you will swap the position
198.495 -> So we will get a new answer
201.588 -> like if you see here
203.156 -> this is 1,2,3 and this is 1,3,2
204.755 -> So what happened 2 and 3 swapped their positions
207.042 -> Right
209.32 -> 3 and 2 have swapped their positions
210.968 -> Similarly what has happened here
212.827 -> 1 and 2 have swapped their positions
214.651 -> Here they are swapped 2 times
216.307 -> Okay
216.995 -> Now similarly multiple swaps have happened
219.126 -> How multiple swaps come
220.514 -> We will discuss that
221.506 -> Let's start
222.97 -> That we have 1,2,3
226.676 -> so what options does 1has
228.037 -> either 1 can remain at its own place
229.585 -> or it can take 2's place
231.269 -> or it can take 3's place
232.852 -> So we write all the three options
234.678 -> That 1 said
236.5 -> I do not need your place
238.257 -> Take it
239.186 -> I will remain where I am
240.467 -> Then 1 said
241.982 -> 2's place seems better
243.805 -> so 2 come here
244.919 -> Let me sit in middle
246.282 -> So this time 1 said, it doesn't feel good at 2's place
248.859 -> Let's sit on 3
249.915 -> So we got these 3 initial options
252.962 -> Now what we left with
254.815 -> Now we can only swap these 2 here
256.688 -> We can swap there 2 here, these 2 here
259.338 -> Then also we will have 2-2 options for everyone
261.568 -> One time we will say
263.595 -> 2 , are you liking your position
265.496 -> It will say that yes I am liking it
266.739 -> So you stay there
268.505 -> Once it will say
271.642 -> I am not liking it
272.909 -> Let's change with three
274.52 -> So once it will change with 3
276.407 -> Here same thing will happen
278.143 -> 1 will say , that I am liking it
279.993 -> I am liking sitting in middle
281.626 -> Once it will say, let's try sitting in the last
283.801 -> It feels good sitting in the last
285.352 -> once it will say, let's keep sitting here
287.292 -> why to go in the last
288.229 -> And once it will say , let's go in the last
290.708 -> So in this way we got same options here
295.026 -> Okay
295.617 -> 6 permutations created
298.032 -> What we did in it
299.16 -> We went every time
300.478 -> We swapped on the element that is on the right from the current index
304.447 -> And said keep swapping it
307.437 -> Because you see
308.533 -> What are the options do we have
309.494 -> In starting we have 3 options
311.213 -> So i have 3 options
313.648 -> Either stay at its own place
314.882 -> or go ahead
316.228 -> or go here
316.943 -> If it comes on second position, then it has only two options
319.048 -> Either stay at its own place
319.951 -> or move ahead
320.747 -> If it came in the last, then it has only one option
322.661 -> It will have to stay at its own position
324.171 -> We cannot do anything
325.33 -> So we did the same here
326.748 -> Now let's write its code
329.046 -> With code, we will dry run it
330.696 -> Then you will understand it better
332.161 -> Okay
333.221 -> So what is it saying that give all the options in the form of a vector and vector format
337.585 -> Let's make a global vector
339.288 -> Okay
340.171 -> It seems easy doing in this way
341.593 -> It is easy to explain otherwise we have to use pass by value pass by reference
345.434 -> That we are not doing right now
347.277 -> Okay
348.081 -> Let's make a helper function
349.402 -> We passed vector
351.83 -> int n and nums
356.689 -> And we passed here int
358.944 -> index i
360.107 -> Now what should be the base condition
362.261 -> pause and think
363.855 -> Your base condition will be same
365.315 -> That when the value of i reached greater than all the sum , numbers
369.722 -> So say bye bye
371.684 -> You cannot move ahead
372.933 -> So when you will reach nums.size
376.7 -> So what we will say
378.015 -> That push back this vector answer in our answer
381.998 -> Means put it in its answer
385.36 -> And go back
387.972 -> do backtrack
389.317 -> Your work has been done
390.117 -> Now what we thought next
391.676 -> That we have to keep swapping in all
393.628 -> So what we will be needed
394.65 -> That we will have to apply a loop
395.759 -> That is starting from i
397.159 -> Okay
398.309 -> And j will go till nums.size
402.965 -> Right
404.104 -> And we will ++ j every time
406.099 -> Now what we have to do
407.415 -> We have to swap
408.168 -> Do swap
409.725 -> nums.i
411.517 -> with nums.j
414.802 -> Okay
416.36 -> After that, we will say
417.816 -> swap happened
419.081 -> Now go helper
420.284 -> From the front of new nums
423.763 -> means from index i + 1
425.486 -> Make all the answers that can be made by swapping
428.097 -> And after that what we will have to do
429.609 -> We will have to bring it to the normal state
431.1 -> Because we are doing changes in original string , original array
433.553 -> Okay
435.143 -> So we will have to bring it in the original state
438.042 -> With whom we started
439.373 ->
441.055 -> This is called doing backtracking
444.306 -> Now what is this backtrack
448.042 -> We will understand backtracking and all in upcoming videos
450.668 -> So in that I will show you what is the difference between backtracking and recursion
453.657 -> backtracking is a problem solving approach
456.32 -> Brute force one
457.025 -> But we cut in between in that
459.083 -> There is no point of moving further from it
460.609 -> Let's leave
461.067 -> But here we are bringing it in normal state
464.558 -> Come back in normal state
466.552 -> And your work is done
468.02 -> From here we will return
469.599 -> Then we will tell helper
471.428 -> Now we will tell helper
475 -> That go
476.365 -> take nums array
477.555 -> start from p0 index
479.073 -> And do all the work
480.146 -> And let me return the answer here
482.163 -> Okay
482.888 -> Let's run our code
484.284 -> So it passed
486.965 -> Now let's try submitting it once
488.193 -> Are you seeing?
490.923 -> 0 seconds
492.399 -> 100% better than C++ other's solutions
495.48 -> This question was last tried in 2020
498.172 -> After that we are coding it for the first time
499.583 -> So let's take its screenshot
501.321 -> Let it explain to you
502.21 -> That what is the scene
503.637 -> So what we had
505.693 -> We are given here num 1,2,3
508.547 -> Our I is currently 0
510.345 -> Okay
511.716 -> We said
512.519 -> Is value of i is equal to size?
514.687 -> i will say no
515.554 -> it is currently 0
516.358 -> So it will not go in the if
517.981 -> It will go here directly
518.581 -> Okay
519.209 -> We will have a j variable
520.666 -> Whose value we will start from 0
521.85 -> And will let it go till 3
523.109 -> So swap will say
524.289 -> Swap 0,0
525.284 -> That was our first case
526.697 -> That you stay there
528.829 -> I like my position
529.752 -> After that what will we do
530.708 -> i, 0+1 is 1
532.612 -> So we will come to the first index
534.037 -> After coming to first index we will say
535.568 -> That is the value of 1 is equal to 3
538.282 -> it is not
538.715 -> So we will not go in the f
539.726 -> We will come down , and say do swap
541.909 -> the j
543.197 -> what will be the value of j here
544.28 -> It is i
544.995 -> So here it will be 1
545.887 -> Okay
547.071 -> on 1 it will say
548.063 -> swap with 1
549.15 -> it will say to 2
550.106 -> you swap with yourself
551.17 -> It said okay
552.677 -> let me swap with myself
553.814 -> It will be swapped with itself
555.248 -> Now recursion will say it that call again
557.635 -> Once more
558.545 -> Okay let's obey recursion
560.95 -> i became 1 from 0.let's do it 2 from 1
563.969 -> let's call on 2 again
565.275 -> we reached at 2 position here
566.802 -> What we will say
567.709 -> here 1,2,3
570.254 -> this will come again and say is the size of 2 equal to num
573.59 -> It will say size is not equal
575.088 -> Will not go to this
575.979 -> Then again come
576.752 -> It will start from j = 2
579.453 -> it will come to 2
580.329 -> it will swap 2 with 2
581.465 -> Okay
582.112 -> And it will call after adding 2+1
584.151 -> It will see here that if the size become equal ? is 3=3
587.242 -> This will add and return from here
588.873 -> From here it will say we got a answer
590.812 -> Go back
591.688 -> It will go back
593.055 -> We will again swap this
595.736 -> 3 was 3, so no benefit of swapping
598.431 -> Okay
598.973 -> Now from here we will go back again
600.364 -> to index 1
601.518 -> we will go to index 1
602.793 -> We will tell index 1 that swap again
604.328 -> index n1 was 2, so no benefit
606.683 -> so chill
608.217 -> Now what will happen after that
609.136 -> It will become 2 from 1 after incrementing in j
611.178 -> when j will become 2 from 1, then we will say swap this with 2
614.371 -> interchange the position of 2 and 3
616.235 -> And call this
618.436 -> interchanged position of 2
619.833 -> i's value became 2 from 1
622.522 -> after 2, we again checked
624.022 -> is 2= 3 her?, no
626.332 -> so we will not go inside
627.771 -> Will come here directly
628.626 -> will start j's value from 2
629.924 -> 2 is there
631.506 -> so we will swap 2 with 2
632.992 -> Then will tell it that call again with 3
636.04 -> it will call from 3
637.108 -> So it will again come 1,3,2
639.724 -> Doing like this, we will go to everyone
641.627 -> will keep backtracking with everyone
643.155 -> All the part after this
644.889 -> make recursive tree by yourself
646.382 -> This is your homework
650.289 -> Okay
651.355 -> You will make recursive tree
652.419 -> You will understand this code more better
654.433 -> We are doing nothing
655.212 -> All the indexes that are possible
659.035 -> We are trying to go ahead of its right
664.274 -> We are not going back
665.201 -> If you would write 0 here
666.86 -> So it would check at all
668.009 -> That became a very big
670.916 -> That would give you TLE
671.949 -> And it happened
673.118 -> You check this code
675.344 -> And try
676.703 -> If you want to understand anything, drop in the comments section
678.19 -> This was all in today's video
679.254 -> let's meet in another video
680.001 -> Till then bye
Source: https://www.youtube.com/watch?v=b1iFSSxg9Y8