# Permutations II

## Question

### Problem Statement

Given a list of numbers with duplicate number in it. Find all unique permutations.

#### Example

For numbers [1,2,2] the unique permutations are:

[

[1,2,2],

[2,1,2],

[2,2,1]

]

#### Challenge

Do it without recursion.

## 题解1 - backtracking

1. $[1, 2_1, 2_2]$
2. $[1, 2_2, 2_1]$
3. $[2_1, 1, 2_2]$
4. $[2_1, 2_2, 1]$
5. $[2_2, 1, 2_1]$
6. $[2_2, 2_1, 1]$

### C++

class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
vector<vector<int> > permuteUnique(vector<int> &nums) {
vector<vector<int> > ret;
if (nums.empty()) {
return ret;
}

// important! sort before call backTrack
sort(nums.begin(), nums.end());
vector<bool> visited(nums.size(), false);
vector<int> list;
backTrack(ret, list, visited, nums);

return ret;
}

private:
void backTrack(vector<vector<int> > &result, vector<int> &list, \
vector<bool> &visited, vector<int> &nums) {
if (list.size() == nums.size()) {
result.push_back(list);
// avoid unnecessary call for for loop, but not essential
return;
}

for (int i = 0; i != nums.size(); ++i) {
if (visited[i] || (i != 0 && nums[i] == nums[i - 1] \
&& !visited[i - 1])) {
continue;
}
visited[i] = true;
list.push_back(nums[i]);
backTrack(result, list, visited, nums);
list.pop_back();
visited[i] = false;
}
}
};

### 源码分析

Unique Subsets 和 Unique Permutations 的源码模板非常经典！建议仔细研读并体会其中奥义。

## 题解2 - 字典序

Permutation 的题使用字典序的做法其实更为简单，且为迭代的解法，效率也更高。代码和之前的 Permutations 那道题一模一样。

### Java

class Solution {
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (nums == null || nums.size() == 0) return result;

// deep copy(do not change nums)
List<Integer> perm = new ArrayList<Integer>(nums);
// sort first!!!
Collections.sort(perm);

while (true) {
// step0: add perm into result

// step1: search the first num[k] < num[k+1] backward
int k = -1;
for (int i = perm.size() - 2; i >= 0; i--) {
if (perm.get(i) < perm.get(i + 1)) {
k = i;
break;
}
}
// if current rank is the largest, exit while loop
if (k == -1) break;

// step2: search the first perm[k] < perm[l] backward
int l = perm.size() - 1;
while (l > k && perm.get(l) <= perm.get(k)) l--;

// step3: swap perm[k] with perm[l]
Collections.swap(perm, k, l);

// step4: reverse between k+1 and perm.length-1;
reverse(perm, k + 1, perm.size() - 1);
}

return result;
}

private void reverse(List<Integer> nums, int lb, int ub) {
for (int i = lb, j = ub; i < j; i++, j--) {
Collections.swap(nums, i, j);
}
}
}