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) {
                res.add(new ArrayList<Integer>(onePerm));
                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;
                    onePerm.add(num[i]);

                    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)
	                    singlePerm.add(index, insertNum);
	                    tmpList.add(new ArrayList<Integer>(singlePerm));

	                    // @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<>();
	        hs.addAll(list);
	        list.clear();
	        list.addAll(hs);

	        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) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            path.add(nums[i]);
            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([])
        nums.sort() # added for lc-47

        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:
                    visited.add(i)
                    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;
            }
            set.add(nums[j]);
            [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())
        {
            results.Add(new List<int>(temp));
            return;
        }
        var keys = count.Keys.ToList();
        foreach (var key in keys)
        {
            temp.Add(key);
            --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
    }
}

47 - Permutations II

Question

Algorithm

Note

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

All Problems

All Solutions