void print(vector<int>& v){
        for(auto ele : v)
            cout << ele << " ";
        cout<< endl;
    }
    void backtrack(int index, vector<int> ans){
        if(index == (ans.size() - 1)){
            print(ans);
            return;
        }
        for(int i = index; i < ans.size(); i++){
            swap(ans[index], ans[i]);
            backtrack(index+1, ans);
            swap(ans[index], ans[i]);
        }
    }

# nums = list

def permuteUnique(self, nums):
    res, visited = [], [False]*len(nums)
    nums.sort()
    self.dfs(nums, visited, [], res)
    return res
    
def dfs(self, nums, visited, path, res):
    if len(nums) == len(path):
        res.append(path)
        return 
    for i in xrange(len(nums)):
        if not visited[i]: 
            if i>0 and not visited[i-1] and nums[i] == nums[i-1]:  # here should pay attention
                continue
            visited[i] = True
            self.dfs(nums, visited, path+[nums[i]], res)
            visited[i] = False

# nums = list

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            #return # backtracking
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)