usually neetcode has the best solutions/explanations but i gotta say this is the first time ive seen him have the most confusing one lol. Maybe there's a reason he did it this way that will be beneficial for us down the line but it seems to be the worst solution for permutations ive seen. maybe because of that i should understand it lol. i love neetcode btw - best youtuber by far.
Every time I feel stupid and not able to solve a leetcode question, I get to your video for the explanation and the moment I realize the video has 200k+ views I understand that I"m not stupid, just a regular human like hundreds of thousands others.
@@adama7752 how to do that practice. Whenever I try to solve such a leetcode problem I struggle a lot. At the end of the day I search for answers and solve them on my own. But I want to solve a problem of my own without any video or references.
We can avoid popping elements and passing in the remaining list by simply swapping elements. Anyways, an alternative backtracking approach for those who are interested (very short, code, too!): def permute(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(i): if i >= len(nums): res.append(nums[:]) for j in range(i, len(nums)): nums[i], nums[j] = nums[j], nums[i] backtrack(i+1) nums[i], nums[j] = nums[j], nums[i] backtrack(0) return res
Hi, actually we can also use this template - class Solution: def permute(self, nums: List[int]) -> List[List[int]]: result = [] n = len(nums) def backtrack(perm): if len(perm) == len(nums): result.append(perm.copy()) return for i in range(n): if nums[i] in perm: continue perm.append(nums[i]) backtrack(perm) perm.pop() backtrack([]) return result This is similar to how we solve combination problem , we have to do some slight modification .
We can use the index of nums array itself and compute the permutations instead of popping the elements from the beginning and appending it later def permute(self, nums: List[int]) -> List[List[int]]: """ Angle of Attack - use recursive method - base case when one element - recursive call to compute permutation except that element
""" result = list() # base case -- least valid input if len(nums) == 1: return [nums]
for idx in range(len(nums)): # compute the permutation for ith element current_nums = nums[:idx] + nums[idx+1:] # recursive case perms = self.permute(current_nums) # permutation generated above don't have the # ith element, so append it for perm in perms: perm.append(nums[idx])
# update the overall results with all (multiple) permutations result.extend(perms) #return all permutations return result
lmao this video was so good I watched the first few minutes of it and was able to code the problem myself. I then coded another leetcode medium backtracking by myself based on the intuition i got from this video all by myself with 86% time complexity. And these are the first 2 times I have ever done a back tracking problem. you are good asf dude.
Hey, I have used the same tree but a slightly diff approach where u call recursion if that element doesn't exist in perm array def permute(self, nums: List[int]) -> List[List[int]]: res = []
def backtrack(perm): # base case if len(perm) == len(nums): res.append(perm) return for num in nums: if num not in perm: backtrack(perm + [num])
Thank you for alll you do @NeetCode slightly more intuitive for me our remaining choices keep shrinking class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ result = [] def generate_permutations(permutation, remaining): if not remaining: result.append(permutation) return for i in range(len(remaining)): generate_permutations(permutation + [remaining[i]], remaining[:i] + remaining[(i + 1):]) generate_permutations([], nums) return result
Thank you! Backtracking builds potential candidates to solution and abandons a candidate if it no longer leads to a valid solution - this is also called pruning the recursion tree. Can anyone please explain in which instance do we abandon a candidate here? I just want to understand why it falls in backtracking category
we can use the similar approach like problem 17, the only difference is string and list. list needs deep copy. just a little bit slower than average. 17: rs = [] def loop(k,v): if k == len(digits): rs.append(v) return for vv in hashmap[digits[k]]: loop(k+1,v+vv) if digits: loop(0,"") return rs 46 rs = [] def loop(k,v): if k==len(nums): rs.append(v) return for vv in nums: tmp=v[:] if vv not in tmp: tmp.append(vv) loop(k+1,tmp) loop(0,[]) return rs
Why is that local variable : "result" won't initialize when "perm = self.permute(nums)" been executed? Isn't it better to avoid setting a local variable when dealing with a recursion function?
Note that all possible permutations of one array with distinct integers is """pop one from the array, and find all possible permutations from the exist""" . For example, for array like [1, 2, 3], first pop one from it, like 1, then 1 is the first number of the permutation we are finding. Now arrray [2, 3] remains. Continue to find until there's only one number that has not been processed.(Constrain: nums.length >= 1) Add it after the permutation and append to the result list. def permute(self, nums: List[int]) -> List[List[int]]: res = [] cur_permu = [] def dfs(cur_list): if len(cur_list) == 1: res.append(cur_permu.copy() + cur_list) return for index, num in enumerate(cur_list): cur_permu.append(num) dfs(cur_list[:index] + cur_list[index + 1:]) cur_permu.pop()
dfs(nums) return res this solution is really efficient.
I think you're doing duplicate work here. For example, if nums = [1, 2, 3, 4, 5, 6] Then you would call: permute([1, 2, 3, 4, 5]) + append 6 on everything returned and: permute([1, 2, 3, 4, 6]) + append 5 on everything returned However, that means you'll be computing permute([1, 2, 3, 4]) twice, which is inefficient. You can make this more efficient by starting from the bottom up. i.e. [1] -> [1, 2], [2, 1] - > [1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1] Here, for each permutation of the length n, you create n+1 new lists of length n+1 where you insert the new number into every possible position. This way, you only calculate each sub-permutation once
I wrote it differently. Might or might not be more useful def permute(self, nums: List[int]) -> List[List[int]]: # Create a list to store the output and a set to keep track of all the taken numbers output, taken = [], set() # Create a function to take every permutation of unique numbers def permutations_generator(permutation: list): # Base case if the length of permutation is equal to number of elements in nums if len(permutation) == len(nums): output.append(permutation.copy()) return # Go through each number in nums and add that into permutation list if its unique for number in nums: if number not in taken: permutation.append(number) taken.add(number) # Run permutations_generator after adding one number permutations_generator(permutation=permutation) # After the permutations_generator has completed, remove the added numbers for further processing permutation.pop() taken.remove(number) permutations_generator(permutation=[]) return output
solution in c++ class Solution { // vector array for result vector> result;
// set to remember which element is already selected set st; void permutation(vector &nums, vector &res) { // if the size of res become size of num pushed res in result vector and array
if (res.size() == nums.size()) { result.push_back(res); return; }
for (int i = 0; i < nums.size(); i++) { // check if the current number is not chosen
if (st.find(nums[i]) == st.end()) { // insert number in set to remember that the following number is already selected st.insert(nums[i]);
// insert current number in res array res.push_back(nums[i]);
// recursively call permutation to select another number permutation(nums, res);
// on backtrackingremove the current selected number from selected because we are done with possible solution with that selected number st.erase(nums[i]);
class Solution: def permute(self, nums): res =[] perm= [] def dfs(): if len(perm) == len(nums): res.append(perm.copy()) return for n in nums: if n not in perm: perm.append(n) dfs() perm.pop() dfs() return res
My thought is initially the same with Neetcode. I draw a decision tree from an empty list. So I write this code for a straight forward understanding. def permute(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(nums, perm): if not nums: res.append(perm) return for i in range(len(nums)): backtrack(nums[: i] + nums[i + 1:], perm + [nums[i]]) backtrack(nums, []) return res
O(n*n!) for time. The way I thought about it is that there are n! permutations for an array of length n. For each permutation, we need to make n calls to get to the leaves (permutations), so O(n * n!). As for space, I think it's O(n!). We have to store n! permutations.
Hey @NeetCode would be a issue if we do the following: Its TC is still seems to same as n.n! and SC - n stack = [] set_ = set() output = [] def backTrack(): if len(stack)==len(nums): output.append(list(stack)) return for i in range(len(nums)): if nums[i] not in set_: stack.append(nums[i]) set_.add(nums[i]) backTrack() stack.pop() set_.remove(nums[i]) backTrack() return output
Say if for the base case, [nums] instead of [nums[:]] is returned, perms = self.permute(nums) essentially becomes perms = [nums] (note nums is a list), and the iterator perm in perms is now equivalent to nums. perm.append(n) modifies not only perm, but also nums which shares the reference of perm. To see the difference, you can do a print(perm) and print(nums), or print(perm==nums) after perm.append(n) in for perm in perms loop.
Really good video - makes concepts so much easier to understand! But I do have a question, why do you return [nums.copy()] instead of. just [nums] as a base case?
5:17 code only gives 1x of undo swap function and you can only access this function once you are done with the recusive calls and has printed the array result of one such permutation, how are you able to go back up more than one iterations above? That's what you need to explain
Simple java solution: class Solution { List result = new ArrayList(); public List permute(int[] nums) { rec(nums, new HashSet(), new ArrayList()); return result; } private void rec(int[] nums, Set used, List temp) { if (temp.size() == nums.length) { result.add(temp); } for (int i=0; i < nums.length; i++) { if (!used.contains(i)) { Set newUsed = new HashSet(used); newUsed.add(i); List newTemp = new ArrayList(temp); newTemp.add(nums[i]); rec(nums, newUsed, newTemp); } } } }
Easier version, the way neetcode did it for combinations: class Solution: def permute(self, nums: List[int]) -> List[List[int]]: visit = set() res = [] n = len(nums) def backtrack(permute, visit): if len(permute) == len(nums): res.append(permute.copy()) return for i in range(len(nums)): if nums[i] not in visit: permute.append(nums[i]) visit.add(nums[i]) backtrack( permute, visit ) visit.remove(nums[i]) permute.pop() backtrack([], visit) return res
I think use `splice` is more easy to track and understand, and Permutations || also can use the same code to add some condition to solve. /** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { let res = []; if (nums.length === 1) { return [nums.slice()]; } for(let i = 0; i < nums.length; i++) { let n = nums.splice(i, 1)[0] let perms = permute(nums); for(let perm of perms) { perm.push(n); } res = [...res, ...perms]; nums.splice(i, 0, n) } return res; };
Can you please let us know the time complexity of this? It's still gonna be O(∑k=1NP(N,k)) right? Since we are calling the recursive function for every element? It would be helpful if you can elaborate in the comments section and pin it.
my guess is that since we are doing O(n) work per recursive call, and since the algorithm is exponential (two recursive calls with constant difference), the total runtime is O(n2^n)
In python, a list variable is just a pointer pointing to the memory location where the list is present so if you do list1=list2. both list1 and list2 will be same. so eg:- list1=[1,2,3,4,5] list2=list1 list1.pop() print(list1)=======>[1,2,3,4] print(list2)=======>[1,2,3,4] in python id() will give you the memory location. so if you print(id(list1)) the value will be same as id list2 on other hand copy will do a deepcopy of the list and make it a new list with different pointer. so when passing through return etc, if you try changing things in a return list it will also get changed in the original passed variable unless you copy it.
Much easier solution- class Solution: def permute(self, nums: List[int]) -> List[List[int]]: n = len(nums) ans = [] used = set() def dfs(arr): if len(arr) == n: ans.append(arr.copy()) return
for num in nums: if num not in used: used.add(num) arr.append(num) dfs(arr) arr.pop() used.remove(num) dfs([]) return ans
I wrote this: class Solution: def permute(self, nums: List[int]) -> List[List[int]]: """ :type nums: List[int] :rtype: List[List[int]] """ if len(nums) == 1: return [nums] elif len(nums) == 0: return [[]] result = [] sub = self.permute(nums[1:]) for arr in sub: for i in range(len(arr)+1): temp = arr.copy() temp.insert(i, nums[0]) result.append(temp) return result It's almost self explanatory.
@@alwayssporty8102 for i in range(len(nums)): n = nums.pop(i) perms = self.permute(nums) for perm in perms: perm.append(n) result.extend(perms) nums.insert(i, n) you can do this instead it basically takes the digit out from the number and lets the permutation run on rest of the combination of digits.
hey, thanks for the video, extremely informed, just wanted to understand why do we append the removed element to the end of the main array and not at the same position?
Its because we are removing the first element every time. Had it been pop(i) then we would have to insert it at the same position. because we must remove every element at least once. Eg. 1,2,3 first call from this will be per(2,3)(we remove the first element then the list will be 2,3,1 and the second call from the loop will be per(3,1). After that the list will be 3,1,2 and per(1,2) will be called.
Three different ways to solve including Neetcode's solution. And I think this problem's three solutions inspired me so much, so sharing with you guys. def permute(self, nums: List[int]) -> List[List[int]]: if len(nums) == 1: return [nums[:]] res = [] for i in range(len(nums)): n = nums.pop(0) perms = self.permute(nums) for perm in perms: perm.append(n) res.extend(perms) nums.append(n) return res # res = [] # def backtrack(perm): # if len(perm) == len(nums): # res.append(perm.copy()) # return # for i in range(len(nums)): # if nums[i] in perm: # continue # perm.append(nums[i]) # backtrack(perm) # perm.pop() # backtrack([]) # return res # res = [] # def backtrack(nums, perm): # if not nums: # res.append(perm) # return # for i in range(len(nums)): # backtrack(nums[: i] + nums[i + 1:], perm + [nums[i]]) # backtrack(nums, []) # return res
You can optimise your second solution's time complexity by maintaining a set in addition to the perm array that will make "if nums[i] in perms" O(1) constant time as opposed to O(n). The tradeoff is with the space complexity as that will now be slightly less optimal given you have to maintain a hashset that could take O(n) space.
I believe time is O(n!) (maybe O( n! ^2)) because each recursion is looping roughly n^2 then (n-1)^2... (e.g an array of length for is looping roughly 4*3*2*1). Space (Extra not including the result) is O(n), because it's the maximum recursion depth.
Here is a simpler solution that goes very well with the pen and paper method explained in the video to keep things consistent. Cheers! ``` class Solution: def permute(self, nums: List[int]) -> List[List[int]]: if len(nums)==1: return [nums] result = [] for i in range(len(nums)): remaining = [j for j in nums if j!=nums[i]] current_permutation = [nums[i]] self.dfs(remaining, current_permutation, result) return result def dfs(self, remaining, current_permutation, result): # base case if len(remaining)==1: current_permutation.extend(remaining) result.append(current_permutation.copy()) return # take a decision for each remaining element for j in range(len(remaining)): new_remaining = remaining[:j]+remaining[j+1:] self.dfs(new_remaining, current_permutation+[remaining[j]], result) ```
I think building the permutation on the way down is way more intuitive than on the way back up. Please verify my complexity analysis at the bottom: ```python class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] def dfs(cur: list[int], nums: list[int]) -> None: if not nums: res.append(cur.copy()) return for _ in range(len(nums)): cur.append(nums[-1]) temp = nums.pop() dfs(cur, nums) nums.append(temp) cur.pop() nums = nums[1:] + nums[:1] dfs([], nums) return res # O(n! * n) O(n) ```
Am I missing something or is the image at 6:00 not showing what the code is doing? first we have [1,2,3], we pop 1 and permute [2,3] and put 1 at the end. then we have [2,3,1], we pop 2, permute [3,1] and put 2 at the end. but the image is showing that we permute [1,3], not [3,1]. Right? Backtracking is counterintuitive for me so I may be wrong here, but having the image follow the code may help make it easier. great work though!
Same underlying login but more understandable code? Any feedback is appreciated. def permute(self, nums: List[int]) -> List[List[int]]:
res = [] def dfs(cur, temp): if len(temp) == len(nums): res.append(temp.copy()) return for i in range(len(cur)): temp.append(cur[i]) dfs(cur[:i] + cur[i+1:], temp) temp.pop() dfs(nums, []) return res
Did it without the use of pop(0) def permutations_num(nums): result = [] if len(nums) == 1: return [nums[:]] for _ in range(len(nums)): n = nums[0] perms = permutations_num(nums[1:]) for perm in perms: perm.append(n) # [2,3]+[1] and [3,2]+[1] individually result.extend(perms) # [2,3,1],[3,2,1] all together into the result return result print(permutations_num([1,2,3]))
The first few lines of the outer for loop should be like this in order to work for i in range(len(nums)): n = nums[i] perms = permutations_num(nums[:i]+nums[i+1:])
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: result = [] if len(nums) == 1: return [nums[:]] for i in range(len(nums)): n = nums[i] perms = self.permute(nums[:i]+nums[i+1:]) for perm in perms: perm.append(n) # [2,3]+[1] and [3,2]+[1] individually result.extend(perms) # [2,3,1],[3,2,1] all together into the result return result
I still dont get it how u come up with these brilliant ideas?! When i see your solution, i wonder why i dont come with this idea if its so easy? haha Thanks brother!!
It would have been so good for you to explain the deviation from the traditional bactracking approach. This is very hard to understand, very counter intuitive. Still, love your work.
If using mutable collection, time complexity is exactly the space complexity for output: O(n * n!). The list instance is created "only" at the base case. Then the result of base case is always reused and mutated with O(1) time complexity to add single value. Using immutable collection, I am not sure how to compute it but it will be much slower.
Why do I get "RecursionError: maximum recursion depth exceeded while calling a Python object" error when I use "return [nums]" instead of "return [nums[:]]"?
When looping we are not actually using i to access the value, we are always getting pop(0). To get a new element we need to append the old one to the back so that we don't get it again
hey @NeetCode, why we can't simply return [nums] for base condition, I know it is not working but please tell me why we are doing it. at the end we have only one element and we don't need to return like that right.
I rerecorded this solution and made it much better, please watch this instead: th-cam.com/video/FZe0UqISmUw/w-d-xo.html
please add monthly subscription so i can try it before paying full year
@@abdullahtahan please pay yearly subscription as it is more convenient
usually neetcode has the best solutions/explanations but i gotta say this is the first time ive seen him have the most confusing one lol. Maybe there's a reason he did it this way that will be beneficial for us down the line but it seems to be the worst solution for permutations ive seen. maybe because of that i should understand it lol. i love neetcode btw - best youtuber by far.
I agree with your analysis. I was too confused and disappointed in this solution. The editorial solution on LC is neat and easy to understand.
yeah.. this neetcode solution was destroying me until i looked at the leetcode editorial that made perfect sense
I agree with you! I was doubting myself lol this solution doesn't work for me. (I love this guy!)
I felt the same and I was like it's probably only me, glad I'm not the only one, lol. Still love neetcode for all the videos and explanations
i think the idea is sometimes you have to do a bit of the heavy-lifting, cant expect NC to spoonfeed us everything
Every time I feel stupid and not able to solve a leetcode question, I get to your video for the explanation and the moment I realize the video has 200k+ views I understand that I"m not stupid, just a regular human like hundreds of thousands others.
I'm feeling stupid too - I feel incompetent. I thought this would be a walk in the park.
@@dnc077 it's okay bro, it's just training your brain for pattern recognition. It requires effort + time !
@@adama7752 how to do that practice. Whenever I try to solve such a leetcode problem I struggle a lot. At the end of the day I search for answers and solve them on my own. But I want to solve a problem of my own without any video or references.
We can avoid popping elements and passing in the remaining list by simply swapping elements. Anyways, an alternative backtracking approach for those who are interested (very short, code, too!):
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(i):
if i >= len(nums):
res.append(nums[:])
for j in range(i, len(nums)):
nums[i], nums[j] = nums[j], nums[i]
backtrack(i+1)
nums[i], nums[j] = nums[j], nums[i]
backtrack(0)
return res
so beautiful idea, where did you get the inspiration?
I also originally solved it by swapping and undoing the swapping, instead of pop and push into the array.
@@m3hdim3hdi Permutation is just number of ways to put stuff say in a row or on a circle, so swapping is analogous to changing the order in the row.
Thank you for this beautifully intuitive solution
in haskell:
import Data.List
permute :: Eq a => [a] -> [[a]]
permute [] = [[]]
permute xs = [x : ys | x
Hi, actually we can also use this template -
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
n = len(nums)
def backtrack(perm):
if len(perm) == len(nums):
result.append(perm.copy())
return
for i in range(n):
if nums[i] in perm:
continue
perm.append(nums[i])
backtrack(perm)
perm.pop()
backtrack([])
return result
This is similar to how we solve combination problem , we have to do some slight modification .
what's the use of perm here? where we're using it?
@@himanshu6489 perm here is used to store individual permutation
Not as efficient since checking if nums[i] in perm is linear worst case, you could maybe use a set instead to make it constant
@@jorgecabiedes1877 But set will lose the ordering, which we need to preserve in permutations. Hence, we use list
We can use the index of nums array itself and compute the permutations instead of popping the
elements from the beginning and appending it later
def permute(self, nums: List[int]) -> List[List[int]]:
""" Angle of Attack
- use recursive method
- base case when one element
- recursive call to compute permutation except that element
"""
result = list()
# base case -- least valid input
if len(nums) == 1:
return [nums]
for idx in range(len(nums)):
# compute the permutation for ith element
current_nums = nums[:idx] + nums[idx+1:]
# recursive case
perms = self.permute(current_nums)
# permutation generated above don't have the
# ith element, so append it
for perm in perms:
perm.append(nums[idx])
# update the overall results with all (multiple) permutations
result.extend(perms)
#return all permutations
return result
thank u ive been searching forever, this is the only video on this problem with this much effort involved
Thanks, I'm glad it was helpful =)
The nuances of the recursive logic in these problems are so hard to visualize ahh!
No bro you don't need to visualize. You just need to understand the structure of backtracking.
lmao this video was so good I watched the first few minutes of it and was able to code the problem myself. I then coded another leetcode medium backtracking by myself based on the intuition i got from this video all by myself with 86% time complexity. And these are the first 2 times I have ever done a back tracking problem. you are good asf dude.
i think you're good asf for being able to do that based off a few mins of this vid
This guy lying thru his fokin teeth
riiiight
@@fatropolis6909How do you know?
Thanks
How did you map the decision tree to the recursion logic?
Hey, I have used the same tree but a slightly diff approach where u call recursion if that element doesn't exist in perm array
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(perm):
# base case
if len(perm) == len(nums):
res.append(perm)
return
for num in nums:
if num not in perm:
backtrack(perm + [num])
backtrack([])
return res
it's beautiful
@@jason1666most elegant solution:
in haskell:
import Data.List
permute :: Eq a => [a] -> [[a]]
permute [] = [[]]
permute xs = [x : ys | x
Thank you for alll you do @NeetCode
slightly more intuitive for me
our remaining choices keep shrinking
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
def generate_permutations(permutation, remaining):
if not remaining:
result.append(permutation)
return
for i in range(len(remaining)):
generate_permutations(permutation + [remaining[i]], remaining[:i] + remaining[(i + 1):])
generate_permutations([], nums)
return result
Thank you! Backtracking builds potential candidates to solution and abandons a candidate if it no longer leads to a valid solution - this is also called pruning the recursion tree. Can anyone please explain in which instance do we abandon a candidate here? I just want to understand why it falls in backtracking category
We abandon a candidate when we pop(0)
Thank you so much man !! Please don't delete this videos
awesome contents as always. I found your channel to be the best Leetcode problem solution explanation channel on TH-cam!
You know what I about this guy is the ease which he explains the problems I also saw his system design course for beginners ..just wonde
Keep doing this! It's really good!
we can use the similar approach like problem 17, the only difference is string and list. list needs deep copy. just a little bit slower than average.
17:
rs = []
def loop(k,v):
if k == len(digits):
rs.append(v)
return
for vv in hashmap[digits[k]]:
loop(k+1,v+vv)
if digits:
loop(0,"")
return rs
46
rs = []
def loop(k,v):
if k==len(nums):
rs.append(v)
return
for vv in nums:
tmp=v[:]
if vv not in tmp:
tmp.append(vv)
loop(k+1,tmp)
loop(0,[])
return rs
Thanks!
Thank you so much Yiannis!
Why is that local variable : "result" won't initialize when "perm = self.permute(nums)" been executed?
Isn't it better to avoid setting a local variable when dealing with a recursion function?
Is line 14 logically correct?? What does it mean??
for perm in perms:
perm.append(n)
Note that all possible permutations of one array with distinct integers is """pop one from the array, and find all possible permutations from the exist""" . For example, for array like [1, 2, 3], first pop one from it, like 1, then 1 is the first number of the permutation we are finding. Now arrray [2, 3] remains. Continue to find until there's only one number that has not been processed.(Constrain: nums.length >= 1) Add it after the permutation and append to the result list.
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
cur_permu = []
def dfs(cur_list):
if len(cur_list) == 1:
res.append(cur_permu.copy() + cur_list)
return
for index, num in enumerate(cur_list):
cur_permu.append(num)
dfs(cur_list[:index] + cur_list[index + 1:])
cur_permu.pop()
dfs(nums)
return res
this solution is really efficient.
your explanation and solution is pretty fluent.Thanks for a great video,
I think you're doing duplicate work here. For example, if nums = [1, 2, 3, 4, 5, 6]
Then you would call: permute([1, 2, 3, 4, 5]) + append 6 on everything returned
and: permute([1, 2, 3, 4, 6]) + append 5 on everything returned
However, that means you'll be computing permute([1, 2, 3, 4]) twice, which is inefficient.
You can make this more efficient by starting from the bottom up.
i.e. [1] -> [1, 2], [2, 1] - > [1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]
Here, for each permutation of the length n, you create n+1 new lists of length n+1 where you insert the new number into every possible position. This way, you only calculate each sub-permutation once
Thanks! Never thought to think of it in terms of a decision tree.
I wrote it differently. Might or might not be more useful
def permute(self, nums: List[int]) -> List[List[int]]:
# Create a list to store the output and a set to keep track of all the taken numbers
output, taken = [], set()
# Create a function to take every permutation of unique numbers
def permutations_generator(permutation: list):
# Base case if the length of permutation is equal to number of elements in nums
if len(permutation) == len(nums):
output.append(permutation.copy())
return
# Go through each number in nums and add that into permutation list if its unique
for number in nums:
if number not in taken:
permutation.append(number)
taken.add(number)
# Run permutations_generator after adding one number
permutations_generator(permutation=permutation)
# After the permutations_generator has completed, remove the added numbers for further processing
permutation.pop()
taken.remove(number)
permutations_generator(permutation=[])
return output
solution in c++
class Solution
{
// vector array for result
vector> result;
// set to remember which element is already selected
set st;
void permutation(vector &nums, vector &res)
{
// if the size of res become size of num pushed res in result vector and array
if (res.size() == nums.size())
{
result.push_back(res);
return;
}
for (int i = 0; i < nums.size(); i++)
{
// check if the current number is not chosen
if (st.find(nums[i]) == st.end())
{
// insert number in set to remember that the following number is already selected
st.insert(nums[i]);
// insert current number in res array
res.push_back(nums[i]);
// recursively call permutation to select another number
permutation(nums, res);
// on backtrackingremove the current selected number from selected because we are done with possible solution with that selected number
st.erase(nums[i]);
//also remove from res array
res.pop_back();
}
}
}
public:
vector> permute(vector &nums)
{
vector res;
permutation(nums, res);
return result;
}
};
Thank you Neetcode. Can you show the time complexity analysis for this solution?
def permute(self, nums):
resultList = []
self.backtrack(resultList, [], nums)
return resultList
def backtrack(self, resultList, tempList, nums):
if len(tempList) == len(nums):
resultList.append(list(tempList))
return
for number in nums:
if number in tempList:
continue
tempList.append(number)
self.backtrack(resultList, tempList, nums)
tempList.pop()
Such clean solution
and i just come up with this solution
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums)
it seems I fully understand your idea but when it comes to writing code it requires from me a lot thinking, struggling
us bestie
class Solution:
def permute(self, nums):
res =[]
perm= []
def dfs():
if len(perm) == len(nums):
res.append(perm.copy())
return
for n in nums:
if n not in perm:
perm.append(n)
dfs()
perm.pop()
dfs()
return res
your ans is super clear, much better than the leetcode official one. Liked
thanks man, i had hard time understanding this problem but this video helped a lot!
My thought is initially the same with Neetcode. I draw a decision tree from an empty list. So I write this code for a straight forward understanding.
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(nums, perm):
if not nums:
res.append(perm)
return
for i in range(len(nums)):
backtrack(nums[: i] + nums[i + 1:], perm + [nums[i]])
backtrack(nums, [])
return res
I had the same solution as you. I think you need to do perm.copy() when you append to res on line 5?
@@danny65769 Yes, you can. But you dont have to. perm is not a global variable, so we can just append perm, not perm.copy()
Could you please tell the time and space complexity of this solution?
O(n*n!) for time. The way I thought about it is that there are n! permutations for an array of length n. For each permutation, we need to make n calls to get to the leaves (permutations), so O(n * n!). As for space, I think it's O(n!). We have to store n! permutations.
Whats the time and space complexity and how can we explain it?
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Great video, can you add in the bookmark for starting explaining the solution like you have in other videos?
def permute(self, nums: List[int]) -> List[List[int]]:
output = []
def backtracking(res):
if len(res) == len(nums):
output.append(list(res))
for i in nums:
if i not in res:
res.append(i)
backtracking(res)
res.pop()
backtracking([])
return output
you should add return after output.append(list(res)), so that base can return from there itself rather than going again into the loop to exit.
thanks
Nice solution
Can you please tell about space and time complexity
Thanks
Can anyone explain how using a slicing operator (nums[:]) made our solution faster compared to nums.copy()
it doesnt. leetcode is just flaky
[:] is a deep copy, not a shallow copy. not sure how it helps tho...
What would be the time complexity of this algorithm?
Hey @NeetCode would be a issue if we do the following:
Its TC is still seems to same as n.n! and SC - n
stack = []
set_ = set()
output = []
def backTrack():
if len(stack)==len(nums):
output.append(list(stack))
return
for i in range(len(nums)):
if nums[i] not in set_:
stack.append(nums[i])
set_.add(nums[i])
backTrack()
stack.pop()
set_.remove(nums[i])
backTrack()
return output
Hi, Thank you for making this video! I have one question though. Why do you need to make a copy of the base case ( nums[:] ) ?
Say if for the base case, [nums] instead of [nums[:]] is returned, perms = self.permute(nums) essentially becomes perms = [nums] (note nums is a list), and the iterator perm in perms is now equivalent to nums. perm.append(n) modifies not only perm, but also nums which shares the reference of perm.
To see the difference, you can do a print(perm) and print(nums), or print(perm==nums) after perm.append(n) in for perm in perms loop.
Deep copy vs shallow copy
@@abishekanbarasan5537 what is the difference?
What is the time and space complexity of this solution?
Really good video - makes concepts so much easier to understand! But I do have a question, why do you return [nums.copy()] instead of. just [nums] as a base case?
To not get caught up in the call by reference problem. By default lists are passed on by reference rather than value.
5:17 code only gives 1x of undo swap function and you can only access this function once you are done with the recusive calls and has printed the array result of one such permutation, how are you able to go back up more than one iterations above? That's what you need to explain
How would this look like in Java? I've been racking my brain on how to not append to sublists that have already been appended to
in Java, you need to add it to the list instead
Simple java solution:
class Solution {
List result = new ArrayList();
public List permute(int[] nums) {
rec(nums, new HashSet(), new ArrayList());
return result;
}
private void rec(int[] nums, Set used, List temp) {
if (temp.size() == nums.length) {
result.add(temp);
}
for (int i=0; i < nums.length; i++) {
if (!used.contains(i)) {
Set newUsed = new HashSet(used);
newUsed.add(i);
List newTemp = new ArrayList(temp);
newTemp.add(nums[i]);
rec(nums, newUsed, newTemp);
}
}
}
}
In the picture explanation, should the second subtree be [3, 1]? We popped the first element from [2, 3, 1]
Yes, you are correct
Easier version, the way neetcode did it for combinations:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
visit = set()
res = []
n = len(nums)
def backtrack(permute, visit):
if len(permute) == len(nums):
res.append(permute.copy())
return
for i in range(len(nums)):
if nums[i] not in visit:
permute.append(nums[i])
visit.add(nums[i])
backtrack( permute, visit )
visit.remove(nums[i])
permute.pop()
backtrack([], visit)
return res
The explanation is beautiful, thanks.
I think use `splice` is more easy to track and understand, and Permutations || also can use the same code to add some condition to solve.
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let res = [];
if (nums.length === 1) {
return [nums.slice()];
}
for(let i = 0; i < nums.length; i++) {
let n = nums.splice(i, 1)[0]
let perms = permute(nums);
for(let perm of perms) {
perm.push(n);
}
res = [...res, ...perms];
nums.splice(i, 0, n)
}
return res;
};
Can you please let us know the time complexity of this? It's still gonna be O(∑k=1NP(N,k)) right? Since we are calling the recursive function for every element? It would be helpful if you can elaborate in the comments section and pin it.
+1 to this
my guess is that since we are doing O(n) work per recursive call, and since the algorithm is exponential (two recursive calls with constant difference), the total runtime is O(n2^n)
@@MasterAraid N factorial N!
Naive question :)
Why do we need to return the copy of the nums arrray?
Sorry I'm stupid.
In python, a list variable is just a pointer pointing to the memory location where the list is present
so if you do list1=list2. both list1 and list2 will be same.
so eg:-
list1=[1,2,3,4,5]
list2=list1
list1.pop()
print(list1)=======>[1,2,3,4]
print(list2)=======>[1,2,3,4]
in python id() will give you the memory location.
so if you print(id(list1)) the value will be same as id list2
on other hand copy will do a deepcopy of the list and make it a new list with different pointer.
so when passing through return etc, if you try changing things in a return list it will also get changed in the original passed variable unless you copy it.
Much easier solution-
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
used = set()
def dfs(arr):
if len(arr) == n:
ans.append(arr.copy())
return
for num in nums:
if num not in used:
used.add(num)
arr.append(num)
dfs(arr)
arr.pop()
used.remove(num)
dfs([])
return ans
I wrote this:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 1:
return [nums]
elif len(nums) == 0:
return [[]]
result = []
sub = self.permute(nums[1:])
for arr in sub:
for i in range(len(arr)+1):
temp = arr.copy()
temp.insert(i, nums[0])
result.append(temp)
return result
It's almost self explanatory.
Very well explained. Thanks a lot!
hey can u explain what the 10th line exactly does how does it gives all permutations of the remaining 2 digits??
@@alwayssporty8102
for i in range(len(nums)):
n = nums.pop(i)
perms = self.permute(nums)
for perm in perms:
perm.append(n)
result.extend(perms)
nums.insert(i, n)
you can do this instead
it basically takes the digit out from the number and lets the permutation run on rest of the combination of digits.
tq very much i learnt more of dsa by your problems
hey, thanks for the video, extremely informed, just wanted to understand why do we append the removed element to the end of the main array and not at the same position?
Its because we are removing the first element every time. Had it been pop(i) then we would have to insert it at the same position. because we must remove every element at least once. Eg. 1,2,3 first call from this will be per(2,3)(we remove the first element then the list will be 2,3,1 and the second call from the loop will be per(3,1). After that the list will be 3,1,2 and per(1,2) will be called.
Most beautiful code. I had to use a visualizer to fully understand it though.
what visualizer?
@@ballzi3122 To debug the code you can use some tools instead of doing it yourself. Specially useful with problems that have recursion.
What's the time complexity?
Three different ways to solve including Neetcode's solution. And I think this problem's three solutions inspired me so much, so sharing with you guys.
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 1:
return [nums[:]]
res = []
for i in range(len(nums)):
n = nums.pop(0)
perms = self.permute(nums)
for perm in perms:
perm.append(n)
res.extend(perms)
nums.append(n)
return res
# res = []
# def backtrack(perm):
# if len(perm) == len(nums):
# res.append(perm.copy())
# return
# for i in range(len(nums)):
# if nums[i] in perm:
# continue
# perm.append(nums[i])
# backtrack(perm)
# perm.pop()
# backtrack([])
# return res
# res = []
# def backtrack(nums, perm):
# if not nums:
# res.append(perm)
# return
# for i in range(len(nums)):
# backtrack(nums[: i] + nums[i + 1:], perm + [nums[i]])
# backtrack(nums, [])
# return res
You can optimise your second solution's time complexity by maintaining a set in addition to the perm array that will make "if nums[i] in perms" O(1) constant time as opposed to O(n). The tradeoff is with the space complexity as that will now be slightly less optimal given you have to maintain a hashset that could take O(n) space.
@@DhruvOberoi yup
I think the 3rd solution is easiest to understand.
no need to pop and appened if you just swap the elements and shift start position and swap them back afterwards.
But this code does not work on leetcode. It gives errors
I have watched this three times, this was complicated.
How to do it lexicographically without using internal function for permutations (from itertools)?
This solution doesn't use itertools....
What about using python's itertools? How does it compare in terms of time?
you dont use itertools in dsa questions it defeats the purpose
I'm crying -- multiple comments begging for the time / space complexity and still no answer... i am also begging
I believe time is O(n!) (maybe O( n! ^2)) because each recursion is looping roughly n^2 then (n-1)^2... (e.g an array of length for is looping roughly 4*3*2*1). Space (Extra not including the result) is O(n), because it's the maximum recursion depth.
Why would you have getting the subPermutations in side the first for loop? That seems like a needless performance overhead.
Here is a simpler solution that goes very well with the pen and paper method explained in the video to keep things consistent. Cheers!
```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums)==1:
return [nums]
result = []
for i in range(len(nums)):
remaining = [j for j in nums if j!=nums[i]]
current_permutation = [nums[i]]
self.dfs(remaining, current_permutation, result)
return result
def dfs(self, remaining, current_permutation, result):
# base case
if len(remaining)==1:
current_permutation.extend(remaining)
result.append(current_permutation.copy())
return
# take a decision for each remaining element
for j in range(len(remaining)):
new_remaining = remaining[:j]+remaining[j+1:]
self.dfs(new_remaining, current_permutation+[remaining[j]], result)
```
can any one plz explain why we need to append n back to nums ? what does it achieve
this was an awesome solution! thanks
I think building the permutation on the way down is way more intuitive than on the way back up.
Please verify my complexity analysis at the bottom:
```python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(cur: list[int], nums: list[int]) -> None:
if not nums:
res.append(cur.copy())
return
for _ in range(len(nums)):
cur.append(nums[-1])
temp = nums.pop()
dfs(cur, nums)
nums.append(temp)
cur.pop()
nums = nums[1:] + nums[:1]
dfs([], nums)
return res
# O(n! * n) O(n)
```
Am I missing something or is the image at 6:00 not showing what the code is doing?
first we have [1,2,3], we pop 1 and permute [2,3] and put 1 at the end.
then we have [2,3,1], we pop 2, permute [3,1] and put 2 at the end. but the image is showing that we permute [1,3], not [3,1].
Right?
Backtracking is counterintuitive for me so I may be wrong here, but having the image follow the code may help make it easier.
great work though!
Love everything you have done but this honestly should be a 25-min video
Same underlying login but more understandable code? Any feedback is appreciated.
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(cur, temp):
if len(temp) == len(nums):
res.append(temp.copy())
return
for i in range(len(cur)):
temp.append(cur[i])
dfs(cur[:i] + cur[i+1:], temp)
temp.pop()
dfs(nums, [])
return res
What would be the time complexity for this algo.?
Did it without the use of pop(0)
def permutations_num(nums):
result = []
if len(nums) == 1:
return [nums[:]]
for _ in range(len(nums)):
n = nums[0]
perms = permutations_num(nums[1:])
for perm in perms:
perm.append(n) # [2,3]+[1] and [3,2]+[1] individually
result.extend(perms) # [2,3,1],[3,2,1] all together into the result
return result
print(permutations_num([1,2,3]))
That's great, I like this one better!
The first few lines of the outer for loop should be like this in order to work
for i in range(len(nums)):
n = nums[i]
perms = permutations_num(nums[:i]+nums[i+1:])
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
if len(nums) == 1:
return [nums[:]]
for i in range(len(nums)):
n = nums[i]
perms = self.permute(nums[:i]+nums[i+1:])
for perm in perms:
perm.append(n) # [2,3]+[1] and [3,2]+[1] individually
result.extend(perms) # [2,3,1],[3,2,1] all together into the result
return result
@NeetCode the pop(0) has O(n) time complexity. This solution might be better.
@@hailei In my interviews, I still resort to Neetcode's solution lol
Hi , whats the time complexity of the solution?
I still dont get it how u come up with these brilliant ideas?! When i see your solution, i wonder why i dont come with this idea if its so easy? haha
Thanks brother!!
in haskell:
import Data.List
permute :: Eq a => [a] -> [[a]]
permute [] = [[]]
permute xs = [x : ys | x
It would have been so good for you to explain the deviation from the traditional bactracking approach. This is very hard to understand, very counter intuitive. Still, love your work.
Why does replacing copy() with [:] make it faster?
why not just return [[nums[0]]] which also work and simpler rather than [nums[:]] ?
NEET CODE INDEED! I wish I've watched your videos earlier. Such clean solution written in Python!
Why do we have to return a copy of nums in the base case and not just nums itself
If using mutable collection, time complexity is exactly the space complexity for output: O(n * n!).
The list instance is created "only" at the base case. Then the result of base case is always reused and mutated with O(1) time complexity to add single value.
Using immutable collection, I am not sure how to compute it but it will be much slower.
@neetcode
Time complexity? Is it n! Only as per standard permutations which would be created...
Why do I get "RecursionError: maximum recursion depth exceeded while calling a Python object" error when I use "return [nums]" instead of "return [nums[:]]"?
Any chance someone could explain the reasoning for inserting specifically at the end of the list at 9:03?
When looping we are not actually using i to access the value, we are always getting pop(0). To get a new element we need to append the old one to the back so that we don't get it again
Actually I am a java fan but your explanation is really helpful. The recursion logic you are using is pretty easy to understand. Thanks!
why not using heap's algorithm ?
Can you show us how its done if it is all possible order of arrangements of a given set [X,Y,Z]
Can you explain what is the Time complexity?
I like your channel and appreciate the time you take. However this solution is too pythonic. Better to swap, backtrack, swap
hey @NeetCode, why we can't simply return [nums] for base condition, I know it is not working but please tell me why we are doing it. at the end we have only one element and we don't need to return like that right.
Can we thank NeetCode enough?
Happy to help :)
Just wrote my own version of the algorithm you explained, thank you so much!