lc47-Permutations II

發表於   |   分類於   |   0 comments   |   
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
35
class Solution {
private:
    vector<int> sol;
    vector<vector<int>> ans;
    
    
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> marked(nums.size(), 0);
        sort(nums.begin(), nums.end());
        permuteUnique_(nums, marked, 0);
        return ans;
    }
    void permuteUnique_(vector<int>& nums, vector<int>& marked, int level) {
        int prev_num;
        //printf("level=%d ", level);
        if (level >= nums.size()) {
            ans.push_back(sol);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (marked[i])
                continue;
            if (i > 0 && (nums[i] == prev_num))
                continue;
            prev_num = nums[i];
            sol.push_back(nums[i]);
            //cout<<sol.size();
            marked[i] = 1;
            permuteUnique_(nums, marked, level + 1);
            sol.pop_back();
            marked[i] = 0;
        }
    }
};