题目：
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].
链接： http://leetcode.com/problems/permutations-ii/
题解：
求全排列，但元素可能有重复。去重复就成为了关键。今天好好思考了一下dfs+回溯，比如1134，最外层就是求出第一个元素，比如 1， 2， 3， 里面的嵌套dfs再负责第二，三，四个元素。 去重复的方法是传递一个visited数组，把排序后相同的元素看成一个cluster，假如nums[i] == nums[i - 1]，但i-1没有被访问过，说明整个cluster不被访问，跳过整个cluster。
Time complexity - O(n!), Space Complexity - O(n)。
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0)
return res;
Arrays.sort(nums);
ArrayList<Integer> list = new ArrayList<Integer>();
boolean[] visited = new boolean[nums.length];
dfs(res, list, nums, visited);
return res;
}
private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int[] nums, boolean[] visited) {
if(list.size() == nums.length) {
res.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0; i < nums.length; i++) {
if(visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) //skip duplicates
continue;
if(!visited[i]) {
visited[i] = true;
list.add(nums[i]);
dfs(res, list, nums, visited);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}
二刷：
Java:
DFS + Backtracking:
一刷写的一坨屎...这遍依然不清不楚。 主要还是用了Permutation的代码，不同的地方是，我们使用了一个数组 - boolean[] visited。这个数组用来在dfs过程中记录已经访问过的值来避免计算重复。同时我们在dfs和backtracking的时候也要回溯这个数组。 经过上述步骤，我们就可以避免在dfs的时候有重复了。比如输入数组为[1, 1, 1]， 则这个最后的结果 {[1, 1, 1]}是在最外层被加入到res中去的。 我们也要注意在遍历数组的时候，假如 visited[i]或者(i > 0 && nums[i] == nums[i - 1] && visited[i - 1])，要continue。
Time Complexity - O(n!)， Space Complexity - O(n)
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
permuteUnique(res, new ArrayList<Integer>(), visited, nums);
return res;
}
private void permuteUnique(List<List<Integer>> res, List<Integer> onePerm, boolean[] visited, int[] nums) {
if (onePerm.size() == nums.length) {
res.add(new ArrayList<>(onePerm));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])) {
continue;
}
visited[i] = true;
onePerm.add(nums[i]);
permuteUnique(res, onePerm, visited, nums);
onePerm.remove(onePerm.size() - 1);
visited[i] = false;
}
}
}
Iterative： Using Next Permutation:
我们依然可以使用Permutation I里面使用了求next permutation的代码， 完全搬移，都不用改的。 时间和空间复杂度还需要好好计算一下。这里有点混。
Time Complexity - O(n!)， Space Complexity - O(n)
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
Integer[] numsInt = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
numsInt[i] = nums[i];
}
res.add(new ArrayList<>(Arrays.asList(numsInt)));
while (hasNextPermutation(numsInt)) {
res.add(new ArrayList<>(Arrays.asList(numsInt)));
}
return res;
}
private boolean hasNextPermutation(Integer[] nums) {
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
for (int j = nums.length - 1; j >= i; j--) {
if (nums[j] > nums[i]) {
swap(nums, i, j);
reverse(nums, i + 1, nums.length - 1);
return true;
}
}
}
}
return false;
}
private void swap(Integer[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void reverse(Integer[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
}
}
三刷:
使用了和上一题一样的代码，也是next permutation的方法。
Java:
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
do {
List<Integer> permu = new ArrayList<>();
for (int num : nums) permu.add(num);
res.add(permu);
} while (hasNextPermutation(nums));
return res;
}
private boolean hasNextPermutation(int[] nums) {
int len = nums.length;
for (int i = len - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
for (int j = len - 1; j > i; j--) {
if (nums[j] > nums[i]) {
swap(nums, i, j);
reverse(nums, i + 1, len - 1);
return true;
}
}
}
}
return false;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void reverse(int[] nums, int i, int j) {
while (i < j) swap(nums, i++, j--);
}
}
Reference：
http://www.cnblogs.com/springfor/p/3898447.html
https://leetcode.com/discuss/25279/a-simple-c-solution-in-only-20-lines
https://leetcode.com/discuss/10609/a-non-recursive-c-implementation-with-o-1-space-cost
https://leetcode.com/discuss/18482/share-my-recursive-solution
https://leetcode.com/discuss/77245/line-python-solution-with-line-handle-duplication-beat-others
https://leetcode.com/discuss/62272/ac-python-clean-solution-108-ms
https://leetcode.com/discuss/55350/short-and-clean-java-solution