Permutations - Leetcode 46 - Python

[@hasferrr]

i think the backtracking solution with decision tree is more intuitive. For each recursion call, you can store the number that has already added to the Answer list into the HashSet, and for each recursion call you can skip the number that already in the HashSet
function permute(nums: number[]): number[][] {
const result = []
const dfs = (set: Set, pm: number[]): void => {
if (pm.length === nums.length) {
result.push([...pm])
return
}
for (let i = 0; i < nums.length; i++) {
if (set.has(nums[i])) {
continue
}
pm.push(nums[i])
set.add(nums[i])
dfs(set, pm)
pm.pop()
set.delete(nums[i])
}
}
dfs(new Set(), [])
return result
}

[@ashkan.arabim]

yeah I thought the same. he's also slicing and inserting in the middle of arrays which are O(n) operations.

[@bobert6259]

I don't think I could've thought of this solution, the one I came up with was the backtracking one, so it's nice to learn a new approach at least!
List copy is O(n) and slicing+inserting is also O(n). The backtracking approach only has a list copy (assuming appending and popping are O(1)).
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
permutations = [] # To store all our permutations
curr_indices = set() # To keep track of the indices used so far
curr_path = [] # What stores the current permutation (temporarily)
size = len(nums) # Store it for readability
def dfs(idx):
if len(curr_indices) == size: # Base case when we find a permutation
permutations.append(curr_path.copy()) # Add a copy of the permutation
return
for i in range(size): # Go over every remaining possible addition
if i not in curr_indices: # Constraint - do not explore already explored index
curr_indices.add(i) # Keep track of added indices
curr_path.append(nums[i]) # Store the updated permutation
dfs((i + 1) % size) # Explore this new branch
curr_indices.remove(i) # Once explored, remove it so this set can be used again
curr_path.pop() # Same reasoning as removing from the set
dfs(0)
return permutations

[@spiceybyte]

I came up with this direction as well, neetcode is usually great but I like this alternative solution better.

[@wussboi]

@@bobert6259 love it. clear and makes sense to me. Here is mine slightly different
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
""" n! permutations """
perms = []
curr_path = []
n = len(nums)
used = [False] * n # track numbers that have be used
def dfs():
# base case to trigger return
if len(curr_path) == n:
perms.append(curr_path.copy())
return
# recursive case
for i in range(n): # try all possible idx until find unused number.
if not used[i]:
# update curr_pth & used vector
curr_path.append(nums[i])
used[i] = True
dfs() # DFS recursion: explore what other numbers can be used
# going up the function stack
curr_path.pop() # remove i'th value from curr_path/used
used[i] = False
dfs()
return perms

[@user-dv7ti2zm9q]

yeah i agree, this is a rare case where neet's solution was harder to grasp

[@riddle-me-ruben]

This is a way better explanation than the old video. I went months with this problem unsolved because I just couldn't understand, but this explanation helped me tremendously. Thanks!

[@Gomeroff]

I live in Russia, a new day has not yet begun, and you are already solving a new problem)

[@dannygarcia7116]

Easy to understand (imo) DFS solution:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(perm):
if len(perm) == len(nums):
res.append(perm[:])
return

for i in range(len(nums)):
if nums[i] in perm:
continue
perm.append(nums[i])
dfs(perm)
perm.pop()

dfs([])
return res

[@1000timka]

this was my solution basically word for word but I think the problem with it is that you add time when you do the check to see if nums[i] is in perm. The overall complexity is still O(n!) so it probably doesn't matter but just something to be aware of yk.

[@AVGVSTVSivlivs]

Swapping indices method for this question is probably more clear and you should also review Longest Palindromic Substring question. Solutions in the other questions are quite optimal.
Thanks a lot!

[@bandarupawankumar7549]

Thank you neetcode for again working on this problem :)

[@johnveracruz2102]

@NeetcodeIO PLS add a functionality on your site to not show the topics for the questions. want to do them in order without knowing the topic. thanks

[@ChandanKumar-hk2ds]

def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(start,curr):
print(curr)
if len(curr) == len(nums):
res.append(curr.copy())
return

for j in range(len(nums)):
if nums[j] not in curr:
curr.append(nums[j])
backtrack(j+1,curr)
curr.pop()
backtrack(0,[])
return res

[@zereftribbiani8130]

I wouldn't recommend this way of doing it since slicing and inserting are O(n) operations

[@jacobli2676]

The subproblem method is so elegant.

[@MyPodie]

Morning Neetcode!

[@pastori2672]

i feel like a time traveler

[@NguyenLe-nw2uj]

me too, i didn't look at the published timestamp, everything is kinda strange tho.

[@user-vu4ng4rb8k]

hey also do video for cherry pickup 1 and bst to sorted DLL

[@jitpatel7692]

You Make it easy, Thank you

[@logn-x5e]

Ok, this one's really the first problem in neetcode150 that is actually VERY easy to understand the goal but I personally find it extremely hard to implement

[@alexprogrammer]

java version of this solution:
class Solution {
public List permute(int[] nums) {
if (nums.length == 0) {
return List.of(List.of());
}
List res = new ArrayList();
List perms = permute(Arrays.copyOfRange(nums, 1, nums.length));
for (List p : perms) {
for (int i = 0; i < p.size() + 1; i++) {
List pCopy = new ArrayList(p);
pCopy.add(i, nums[0]);
res.add(pCopy);
}
}
return res;
}
}

[@mukeshrawat1304]

Is it possible for you to have some sort of poll or something where we could ask for a video solution of a leetcode problem which you haven't already solved. Because there are quite a few problems which don't have a proper solution on TH-cam and God knows when they will appear as POTD.

[@DeathSugar]

I guess thats what his site is for.

[@ethanking123]

This solution doesn't help much. It doesn't provide any useful insights for similar problems, and I'm not sure why it was explained to us.

[@kanjurer]

I actually just solved the problem yesterday lmao

[@ijavd]

Morning

[@pushkarsaini2]

Now Solve 31 Next Permutation

[@m_jdm357]

The worst solution I've seen.

[@NeetCodeIO]

anything specific about it that you did not like?

[@m_jdm357]

@@NeetCodeIO I tried to understand it but it's really bad when debugging or writing down on paper. Really hard to understand. I found this solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(arr):
if len(arr) == len(nums):
res.append(arr.copy())
return

for i in range(len(nums)):
if nums[i] in arr:
continue
arr.append(nums[i])
backtrack(arr)
arr.pop()

backtrack([])
return res
This I got. If no one supports me and everyone thinks your solution is good. Then I'm wrong.

[@yunusemreozvarlik2906]

@@m_jdm357 Actually, I understood the concept better through this video and the solution that is being implemented is similar to yours.
th-cam.com/video/gFm1lEfnzUQ/w-d-xo.html

[@uditisinha305]

you could be a bit nicer :D