Backtracking: Permutations - Leetcode 46 - Python

0:00 - Drawing explanation
6:12 - Coding solution

Leetcode 46
#Coding #leetcode #neetcode

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[reggiehurley]

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.

[jz]

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.

[Grawlix]

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

[sniff]

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.

[Ron-opes]

thank u ive been searching forever, this is the only video on this problem with this much effort involved

[TheElementFive]

The nuances of the recursive logic in these problems are so hard to visualize ahh!

[rahulprasad]

How did you map the decision tree to the recursion logic?

[siddharthgupta]

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 .

[JimmyCheng]

awesome contents as always. I found your channel to be the best Leetcode problem solution explanation channel on Youtube!

[bilalmunawar]

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

[jsarvesh]

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

[likkiii]

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

[sreenivaskrishna]

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)):
+ [remaining[i]], remaining[:i] + remaining[(i + 1):])

generate_permutations([], nums)

return result

[walterchang]

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?

[dzmitryk]

Keep doing this! It's really good!

[prasantheits]

Is line 14 logically correct?? What does it mean??
for perm in perms:
perm.append(n)

[poorpanda]

Thank you so much man !! Please don't delete this videos

[udittalks]

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

[msnhao]

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

[kingrudong]

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.