# Question

Formatted question description: https://leetcode.ca/all/47.html

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

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]


Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

# Algorithm

Due to the possibility of repeated numbers in the input array, if you follow the previous algorithm, there will be repeated permutations. We need to avoid repetition. In the recursive function, we must determine whether the previous number is equal to the current number. If it is equal, and its The value in the corresponding visited is 1, the current number can be used (the reason for this will be explained below), otherwise it needs to be skipped, so that no duplication will occur.

### Note

1 . use the idea of insertion sort: Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration.

2 . to skip duplicates, two ways: 1. act on permutation_I result, use a set to filter duplicated results: bulky and extra o(N) operations and o(N) space 2. truncate during iteration or recursion, but: need sort nums[] array first, extra o(NlogN) operations

# Code

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations_II {

public static void main(String[] args) {
Permutations_II out = new Permutations_II();
Solution_recursion s = out.new Solution_recursion();

List<ArrayList<Integer>> result = s.permuteUnique(new int[]{1,1,2});
System.out.println(result.toString()); // output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
}

// time: O(N)
// space: O(N)
public class Solution_recursion {

ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {

if (num == null && num.length == 0)
return res;

Arrays.sort(num);

dfs(num, new boolean[num.length], new ArrayList<Integer>());

return res;
}

// @para: used by index
private void dfs(int[] num, boolean[] used, ArrayList<Integer> onePerm) {

if (onePerm.size() == num.length) {
return;
}

for (int i = 0; i < num.length; i++) {

// @note: !used[i-1], here “-1” to skip if prev used
if (i > 0 && !used[i - 1] && num[i] == num[i - 1])
continue;

if (!used[i]) {
used[i] = true;

dfs(num, used, onePerm);

onePerm.remove(onePerm.size() - 1);
used[i] = false;
}
}
}
}

public class Solution_hashset_for_unique {
public List<List<Integer>> permuteUnique(int[] nums) {

List<List<Integer>> list = new ArrayList<>();

if (nums == null || nums.length == 0) {
return list;
}

list.add(new ArrayList<Integer>()); // add empty single list, to make below loop going

for (int i = 0; i < nums.length; i++) {

List<List<Integer>> tmpList = new ArrayList<>();
int insertNum = nums[i];

// get each permutations. eg, [1,2], [2,1]
for (List<Integer> singlePerm: list) {

/*
@note: I made big mistake below, in for(): index<list.size(), but inside add one more to list, so infinite loop...
*/

// eg. [1,2] and insert 3, there are 3 insert position
// for (int index = 0; index <= singlePerm.size(); index++) { // @note: the usage of arraylist add() api: add(atIndex, value)
int singleListSize = singlePerm.size();
for (int index = 0; index <= singleListSize; index++) { // @note: the usage of arraylist add() api: add(atIndex, value)

// @note: don't forget roll back
singlePerm.remove(index);
}
}

// udpate list
list = tmpList;
}

/*
* option 1: sort, and skip duplicated digits => o(NlogN)
* option 2: keep all, then remove duplication, each pair comparison => o(N^2)
*/

// hacky way, work based on permutation_I result
Set<List<Integer>> hs = new HashSet<>();
list.clear();

return list;
}

}
}

############

class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int n = nums.length;
boolean[] used = new boolean[n];
Arrays.sort(nums);
dfs(0, n, nums, used, path, res);
return res;
}

private void dfs(
int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (u == n) {
return;
}
for (int i = 0; i < n; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true;
dfs(u + 1, n, nums, used, path, res);
used[i] = false;
path.remove(path.size() - 1);
}
}
}

• // OJ: https://leetcode.com/problems/permutations-ii
// Time: O(N! * N)
// Space: O(N^2)
// Ref: https://discuss.leetcode.com/topic/8831/a-simple-c-solution-in-only-20-lines
class Solution {
private:
vector<vector<int>> ans;
void permute(vector<int> nums, int start) {
if (start == nums.size() - 1) {
ans.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
if (i != start && nums[i] == nums[start]) continue;
swap(nums[i], nums[start]);
permute(nums, start + 1);
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
permute(nums, 0);
return ans;
}
};

• from typing import List
class Solution: # iterative, if new_perm not in new_res
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = [[]]

if nums is None or len(nums) == 0:
return res

for num in nums:
new_res = []
for perm in res:
for i in range(len(perm) + 1):
new_perm = perm[:i] + [num] + perm[i:]
if new_perm not in new_res:  # Check for uniqueness
new_res.append(new_perm)

res = new_res

return res

class Solution: # iterative
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort() # sort the input to handle duplicates
res = [[]]
for num in nums:
new_res = []
for perm in res:
for i in range(len(perm) + 1):
if i > 0 and perm[i - 1] == num: # added for lc-47, hard to get it
break # skip duplicate
new_perm = perm[:i] + [num] + perm[i:]
# or perm.insert(index, num), like in lc-46
new_res.append(new_perm)
res = new_res
return res

############

class Solution: # dfs
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
visited = set([])

def dfs(nums, path, res, visited):
if len(path) == len(nums):
res.append(path + [])
return

for i in range(0, len(nums)):
if i > 0 and nums[i - 1] == nums[i] and i - 1 not in visited: # added for lc-47
continue
if i not in visited:
path.append(nums[i])
dfs(nums, path, res, visited)
path.pop()
visited.discard(i) # remove(i) will throw exception if i not existing

dfs(nums, [], res, visited)
return res


• func permuteUnique(nums []int) [][]int {
n := len(nums)
res := make([][]int, 0)
path := make([]int, n)
used := make([]bool, n)
sort.Ints(nums)
dfs(0, n, nums, used, path, &res)
return res
}

func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {
if u == n {
t := make([]int, n)
copy(t, path)
*res = append(*res, t)
return
}
for i := 0; i < n; i++ {
if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue
}
path[u] = nums[i]
used[i] = true
dfs(u+1, n, nums, used, path, res)
used[i] = false
}
}

• function permuteUnique(nums: number[]): number[][] {
const n = nums.length;
const res: number[][] = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...nums]);
}
const set = new Set<number>();
for (let j = i; j < n; j++) {
if (set.has(nums[j])) {
continue;
}
[nums[i], nums[j]] = [nums[j], nums[i]];
dfs(i + 1);
[nums[i], nums[j]] = [nums[j], nums[i]];
}
};
dfs(0);
return res;
}


• using System.Collections.Generic;
using System.Linq;

public class Solution {
public IList<IList<int>> PermuteUnique(int[] nums) {
var results = new List<IList<int>>();
var temp = new List<int>();
var count = nums.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());
Search(count, temp, results);
return results;
}

private void Search(Dictionary<int, int> count, IList<int> temp, IList<IList<int>> results)
{
if (!count.Any() && temp.Any())
{
return;
}
var keys = count.Keys.ToList();
foreach (var key in keys)
{
--count[key];
if (count[key] == 0) count.Remove(key);
Search(count, temp, results);
temp.RemoveAt(temp.Count - 1);
if (count.ContainsKey(key))
{
++count[key];
}
else
{
count[key] = 1;
}
}
}
}

• use std::collections::HashSet;
impl Solution {
fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
let n = nums.len();
if i == n {
res.push(nums.clone());
return;
}
let mut set = HashSet::new();
for j in i..n {
if set.contains(&nums[j]) {
continue;
}
set.insert(nums[j]);
nums.swap(i, j);
Self::dfs(i + 1, nums, res);
nums.swap(i, j);
}
}

pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(0, &mut nums, &mut res);
res
}
}