47. Permutations II

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

Example:

Input:
 [1,1,2]

Output:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution

(1) Java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return rst;
        }
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        helper(nums, rst, used, new ArrayList<Integer>());
        return rst;
    }

    private void helper(int[] nums, List<List<Integer>> rst, boolean[] used, List<Integer> list) {
        if (list.size() == nums.length) {
            rst.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i != 0 && nums[i-1]== nums[i] && !used[i-1])) {
                continue;
            }
            used[i] = true;
            list.add(nums[i]);
            helper(nums, rst, used, list);
            list.remove(list.size()-1);
            used[i] = false;
        }
    }
}

(2) Python

class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        rst = [[]]
        if not nums:
            return rst
        for num in nums:
            nrst = []
            for l in rst:
                for i in range(len(l)+1):
                    nrst.append(l[:i]+[num]+l[i:])
                    if i < len(l) and l[i] == num:
                        break
            rst = nrst
        return rst

(3) Scala