# LeetCode 047Permutations II

## LeetCode 047 Permutations II Problem

``````class Solution(object):
# def __init__(self):
#     self.result = {}
#
# def permuteUnique(self, num):
#     """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#     if num is None:
#         return []
#     num.sort()
#     self.getPermute([], num)
#     return self.result.values()
#
# def getPermute(self, prefix, rest):
#     ls = len(rest)
#     if ls == 0:
#         return
#     elif ls == 1:
#         temp = prefix + rest
#         stemp = ''.join(str(t) for t in temp)
#         self.result[stemp] = temp
#     else:
#         for i in range(ls):
#             if i + 1 < ls and rest[i] == rest[i + 1]:
#                 continue
#             temp = prefix[:]
#             temp.append(rest[i])
#             self.getPermute(temp, rest[:i] + rest[i + 1:])

def permuteUnique(self, num):
res = []
if len(num) == 0:
return res
self.permute(res, num, 0)
return res

def permute(self, res, num, index):
if index == len(num):
res.append(list(num))
return
appeared = set()
for i in range(index, len(num)):
if num[i] in appeared:
continue
num[i], num[index] = num[index], num[i]
self.permute(res, num, index + 1)
num[i], num[index] = num[index], num[i]

def permuteUnique(self, num):
# iterative solution
res = [[]]
for i in range(len(nums)):
cache = set()
while len(res[0]) == i:
curr = res.pop(0)
for j in range(len(curr) + 1):
# generate new n permutations from n -1 permutations
new_perm = curr[:j] + [nums[i]] + curr[j:]
stemp = ''.join(map(str, new_perm))
if stemp not in cache: