Permutations II - Backtracking - Leetcode 47

0:00 - Read the problem
1:45 - Drawing Explanation
7:42 - Coding Explanation

leetcode 47

#permutations #programming #python

[leoadnan]

As always great way to describing the problem statement and then implementing it in code.

[thanirmalai]

My intial approach was sorting the elements and when the element is similar to the previous element, we can just ignore. Oh am i so wrong. When you try to select an element through swapping, the sorted nature of the array is lost therefore, it is impossible to know whether the current element is already used or not. that is why hashmap is neccessary.This enables us to know whether the element is already used or not

[mostinho]

3:15 why a regular brute force decision tree doesn’t work (produces duplicate permutations because the original array had duplicate numbers)

This happens because you start off two recursive trees with the same number so these sub trees produce duplicates. At the root of the tree you would have two paths that start with 1 and these would produce duplicate permutations.

So we used hashmap (inputNumber to countInInputArray) representation of the input array and work with that, so that instead of the root having two nodes that start with 1, it only has 1 node that starts with 1. This constraint is what prunes duplicate paths from decision tree. It is also applied recursively at all levels

[dorio]

Worst time complexity should be O(N * N!) in case there's no duplicates in input array.

[Avarn]

If anyone is having problems with perm.copy() saying with an Attribute Error: List object has no Attribute to copy, you can use the List keyword "List(perm)" OR you can do what I did which is to take a slice of the list instead: "perm[:]". Either way, excellent solution. The idea of using a Hashmap came to mind but I was struggling with how to make use of it but your video did an amazing job explaining how to utilize it well.

[woodylucas]

It's always that one hater that dislikes something--annoying. Great Conceptual Overview.

[poptart-br]

You can also use Counter from collections, and just super clear video btw! thank you for the neet explanation :3

[alessandrocamillo]

Another excellent video, with amazingly clear explanations. The problem analysis part is extremely educational. Thank you

[shuhaoliang]

Very clear description and explanation. Thank you!

[taimurshah]

your explanations are much better than algoexpert lol

[_Funtime]

Thanks this made it really simple for me to implement in my JS project.
1 Class, 38 lines, 2 "private" methods, and one static "public" method to process any JS map into a list of permutations.






class PermuteMap {
constructor(map, keyValue = null, parent = null) {
if(!map instanceof Map) {
throw new TypeError(`map parameter is not of type Map: ${map}`);
}
if(!parent instanceof PermuteMap) {
throw new TypeError(`parent parameter is not of type PermuteMap: ${parent}`);
}
this.keyValue = keyValue;
this.parent = parent;
this.children = [];
map.forEach((val, key) => {
let newMap = new Map(map);
if(val > 1) {
newMap.set(key, --val);
}else {
newMap.delete(key);
}
this.children.push(new PermuteMap(newMap, key, this));
});
}
getPermutat() {
return (this.parent == null) ? [] :
}
getChildren() {
return (this.children.length == 0) ? this : this.children.reduce((pV, cV) => pV.concat(cV.getChildren()), []);
}
static process(inputMap) {
if(!inputMap instanceof Map) {
console.log(inputMap);
console.log(inputMap instanceof Map);
throw new TypeError(`inputMap parameter is not of type Map: ${inputMap}`);
}
let output = [];
new => {

});
return output;
}
}

let input = new Map();
input.set('purple', 3);
input.set('green', 1);

[sapnavats]

I usually pick up my leetcode problems if you have made a solution video on them because I find your approach quite intutive and easy to follow. But for this one, I think this is simpler approach:

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ans=[]

def dfs(num, scope):
if len(scope)==0:
ans.append(num.copy())


visited=set()
for i in range(len(scope)):
if scope[i] not in visited:
visited.add(scope[i])
dfs(num+[scope[i]], scope[:i]+scope[i+1:])

dfs([], nums)
return ans

[nammi]

The best explanation, everything is crystal clear now.
Commenting for better reach so that youtube algorithm rank this video higher

[ssatriyaa]

feeling dumb everyday, thanks for the explanation

[thanirmalai]

Python make it look so easy. Java is honestly a nightmare

[TechOnScreen]

Can you also simulate the order in which the output will be generated, it will help to imagine the process.

[aniruddhvasishta]

Why can't you just do the same algorithm as in Permutations 1 but make your result a set? Then the duplicate permutations would be avoided and you can convert to a list before returning? Could you also just sort the input and then in the recursion just check if the current decision is the same as the previous one, because that should theoretically get rid of the redundant branches.

[infinitygod]

did any of you get this solution on your own? i feel like its impossible to do a problem unless we have encountered them or similar problems before

[mohamadilhamramadhan]

I solve this problem by modify the solution from Permutation I (still using Tree).

- if array.length === 1 then return the array
- place unique integers (uniqueArray acquired from duplicatesArray) for nodes
- then, for the next nodes, delete from the duplicatesArray of node's number
-

😁

[yuanfeng]

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = set()
n = len(nums)

def back_track(i):
if i==n:
res.add(tuple(nums[:]))

for j in range(i, n):
nums[i], nums[j] = nums[j], nums[i]
back_track(i+1)
nums[i], nums[j] = nums[j], nums[i]

back_track(0)
return res