47-Permutations-II.py

'''Leetcode- https://leetcode.com/problems/permutations-ii/'''
'''
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
'''

defpermuteUnique(nums):
result= []
perms= []
count= {n:0forninnums}
forninnums:
count[n] +=1

defdfs():
iflen(perms) ==len(nums):
result.append(perms.copy())
return

fornincount:
ifcount[n] >0:
perms.append(n)
count[n]-=1

dfs()

count[n] +=1
perms.pop()

dfs()
returnresult

print(permuteUnique([1,1,2])) #[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

#T:O(n.2^n)
#S:O(n)