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].

Method I

用一个map来表示后面的数是否已经选取了。比如[3,1,1,2]，在选第二个数的时候，我们从[1,1,2]中选择第二个数。我们要确保1只被选作第二个数一次。

 1 class Solution {
 2 public:
 3     vector<vector<int> > permuteUnique(vector<int> &num) {
 4         recursive(num, 0, num.size() - 1);
 5         return ret;
 6     }
 7     
 8     void recursive(vector<int> &num, int s, int e) {
 9         if (s > e) {
10             ret.push_back(num);
11             return;
12         }
13         map<int, bool> exch;
14     
15         for (int i = s; i <= e; ++i) {
16             if (!exch[num[i]]) {
17                 exch[num[i]] = true;
18                 swap(num[i], num[s]);
19                 recursive(num, s + 1, e);
20                 swap(num[i], num[s]);
21             }
22         }
23     }
24 private:
25     vector<vector<int> > ret;
26 };

Method II

Method I用的是交换的思想，网上看到另一种方法。先做排序。对于重复的数，在相同的位置只会被选择一次(Line 18)。

比如[1,1,2,3]，第一个1加入之后，第二个1就不会再加入，这样就生成不了序列。第二个1先加入之后，visited[0]=false，可以再加入，这样就生成了以[1,1]开头的合法序列。

通过这种方式，确保了连续数字中，在某一个位置，只有最后一个会成功。

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