全排列算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

    void dfs(int cur) {
        if(path.size() >= s.size()) {
            res.push_back(path);
            return;
        }
        int len= s.size();
        for(int i=0;i<len;++i) {
            //因为上一轮已经全部搜索过了，没必要重复走一遍
            if ( i && s[i] == s[i-1] && visited[i-1]) continue; 
            if(!visited[i]   ) {
                
                visited[i] = true;
                path.push_back(s[i]);
                dfs(cur + 1);
                visited[i] = false;
                path.pop_back();
            }
        }
    }
};