47. Permutations II.md

47. Permutations II (Medium)

[tag] BFS, permutation

'''
1           1
1 1'        1
1 1 2       1 2

1
1 2
1 2 1'

when 1' is same as 1 (nums[i-1]), and 1 is not in the set. skip
and when i in num_set, skip.
1'
1' 1 2
'''
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        temp = []
        ans = []
        num_set = set()
        def dfs():
            if len(temp) == len(nums):
                ans.append(temp.copy())
                return
            for i in range(len(nums)):
                if i in num_set:
                    continue 
                if i > 0 and nums[i] == nums[i-1] and i-1 not in num_set:
                    continue
                temp.append(nums[i])
                num_set.add(i)
                dfs()
                num_set.remove(i)
                temp.pop()
        
        dfs()
        return ans