Question

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

47 Permutations II

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].

@tag-backtracking

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

Java

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;
	    }

	}
}

All Problems

All Solutions