BiruLyu
6/5/2017 - 12:19 AM

## 47. Permutations II(swap).java

``````"""
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],
[2,1,1]
]

TESTCASES:
Input:
[1,1,2]
[1,1,1,1,1]

Output:
[[1,1,2],[1,2,1],[2,1,1]]
[[1,1,1,1,1]]
"""
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [];
nums.sort();
self.backtracking(nums, [], res);
return res;

def backtracking(self, nums, temp, res):

if len(nums) == 0:
return res.append(temp);

for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]: # Avoid Duplication
continue;
self.backtracking(nums[ : i] + nums[i + 1 : ], temp + [nums[i]], res);``````
``````public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
backtracking(nums, temp, res, visited);
return res;
}

private void backtracking(int[] nums, List<Integer> temp, List<List<Integer>> res, boolean[] visited) {
if(temp.size() == nums.length) {
return;
}
for(int i = 0; i < nums.length; i++) {
if((i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])|| visited[i]) continue;
visited[i] = true;
backtracking(nums, temp, res, visited);
temp.remove(temp.size() - 1);
visited[i] = false;
}
}
}``````
``````public class Solution{
public List<List<Integer>> permuteUnique(int[] nums) {

len = nums.length;

r = new ArrayList<>();

permuteUnique(nums, 0);

return r;
}

List<List<Integer>> r;
int len;

void permuteUnique(int[] nums, int p) {

if (p >= len - 1)
{
List<Integer> v = new ArrayList<>(len);
for (int x: nums)
return;
}

int t = nums[p];
for (int i = p; i < len; i++)
{
int x = nums[i];
if (i > p)
{
boolean skip = false;
for (int j = p; j < i; j++)
{
if (nums[j] == x)
{
skip = true;   // skip duplicates
break;
}
}
if (skip)
continue;
}

//swap: p <=> i
nums[p] = x;
nums[i] = t;

permuteUnique(nums, p + 1);

//backtrack
//swap: p <=> i
nums[i] = x;
nums[p] = t;
}
}
}``````