【Leetcode】Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

 1 class Solution {
 2 public:
 3     vector<vector<int> > permuteUnique(vector<int> &num) {
 4         vector<vector<int> > result;
 5         sort(num.begin(), num.end());
 6         vector<bool> used(100, false);
 7         vector<int> path;
 8         dfs(num, path, used, result);
 9         return result;
10     }
11     
12     private:
13     void dfs(vector<int> &num, vector<int> &path, vector<bool> used, vector<vector<int>> &result) {
14         if (path.size() == num.size()) {
15             result.push_back(path);
16             return;
17         }
18         for (size_t i = 0; i < num.size(); ++i) {
19             if (used[i] == false && (i == 0 || num[i] > num[i - 1] || used[i - 1])) {
20                 path.push_back(num[i]);
21                 used[i] = true;
22                 dfs(num, path, used, result);
23                 used[i] = false;
24                 path.pop_back();
25             }
26         } 
27     }
28 };

View Code

与上一题类似，因为数字可能不同需要的处理有：用一个表记录下各位数有没有被用过，当遇到相同数字的时候，只有排在它之前的相等的数字都被用过了才选它(相当于赋予了编号)。