@NeetCodeIO I think this explanation is pretty good, and the python code is actually good at making things less verbose. For other folks not writing in python though, the solution is quite complicated looking (take a look at the c# solution for example). I believe there are like 2 other solutions to this problem that are quite easy to read/write. The first one requires 'swapping' of 2 indexes. The other one is actually the first solution you avoided in this video because of extra book keeping (see below). I think its actually a nice solution. public void dfs(List nums, List subset, List result) { if (subset.Count == nums.Count) { result.Add(new List(subset)); }else { for (int i = 0; i < nums.Count; i++) { if(subset.Contains(nums[i])) continue; subset.Add(nums[i]); dfs(nums, subset, result); subset.RemoveAt(subset.Count -1); } } }
@hasferrr2 ай бұрын
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.arabim2 ай бұрын
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
@AhmadMasud-k9kАй бұрын
yeah i agree, this is a rare case where neet's solution was harder to grasp
@riddle-me-ruben3 ай бұрын
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!
@Gomeroff3 ай бұрын
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.
@pallopbunnak91035 күн бұрын
@@1000timka lol, I hate the "if len(perm) == len(nums):" part too, that's why I have to watch video
@AVGVSTVSivlivs3 ай бұрын
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!
@bandarupawankumar75493 ай бұрын
Thank you neetcode for again working on this problem :)
@logn-x5e2 ай бұрын
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
@PrashamJadhwani17 күн бұрын
i don't understand the time complexity of this. Shouldn't it be O(n! * n) since there are n! permutations and for each permutation there is O(n) operation of insertion?
@foudilbenouci4826 күн бұрын
the n operation inserting is on ( n-1) ! permutations, so it should be O( (n-1)! * n)=O(n!)
@zereftribbiani8130Ай бұрын
I wouldn't recommend this way of doing it since slicing and inserting are O(n) operations
@ChandanKumar-hk2ds28 күн бұрын
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
@johnveracruz21023 ай бұрын
@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
@jacobli2676Ай бұрын
The subproblem method is so elegant.
@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; } }
@Logeshwar-s7m3 ай бұрын
hey also do video for cherry pickup 1 and bst to sorted DLL
@jitpatel76922 ай бұрын
You Make it easy, Thank you
@pastori26723 ай бұрын
i feel like a time traveler
@NguyenLe-nw2ujАй бұрын
me too, i didn't look at the published timestamp, everything is kinda strange tho.
@MyPodie3 ай бұрын
Morning Neetcode!
@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.
@foudilbenouci4826 күн бұрын
I didn t understand the complexities
@mukeshrawat13043 ай бұрын
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 KZbin and God knows when they will appear as POTD.
@DeathSugar3 ай бұрын
I guess thats what his site is for.
@kanjurer3 ай бұрын
I actually just solved the problem yesterday lmao
@pushkarsaini23 ай бұрын
Now Solve 31 Next Permutation
@ijavd3 ай бұрын
Morning
@m_jdm3572 ай бұрын
The worst solution I've seen.
@NeetCodeIO2 ай бұрын
anything specific about it that you did not like?
@m_jdm3572 ай бұрын
@@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.
@yunusemreozvarlik29062 ай бұрын
@@m_jdm357 Actually, I understood the concept better through this video and the solution that is being implemented is similar to yours. kzbin.info/www/bejne/nXfQYp97m9Oti7M