LeetCode 47. 全排列||

LeetCode 47. 全排列

思路：
这道题与上一题的几乎一样，唯一的不同在于不可以返回相同的排列，我们在高中学化学的时候有一个方法叫做同位素标记法，就是把相同的标记一下，以区分同类中的不同，这道题中我们对nums数组排序，使得所有的同类数字，比如1 1 1 排列在一起，这样，可以认为第一个1有个标记1，第二个1有个标记2...，这样只要我们保证使用1的时候是按照顺序使用，如果前面的1没有被使用，后面的1就不可以被使用。

代码：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        st=vector<bool> (nums.size() + 1 ,false);
        path = vector<int> (nums.size());
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        return res;
    }

    void dfs(vector<int> &nums,int u){
        if(u == nums.size()){
            res.push_back(path);
            return;
        }

        for(int i=0;i<nums.size();i++){
            if(!st[i]){
                if(i && nums[i - 1] == nums[i] && !st[i-1]) continue;
                st[i]=true;
                path[u]=nums[i];
                dfs(nums,u+1);
                st[i]=false;
            }
        }

    }
};