Permutations II

---

Permutations II: 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

---

Try this Problem on your own or check similar problems:

1. Permutations
2. Next Permutation
3. Number of Squareful Arrays

Solution:

Java

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

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

                helper(nums, currentList, result, visited);

                currentList.remove(currentList.size() - 1);
                visited[i] = false;
            }
        }
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const result = [];
  nums.sort((a, b) => a - b);
  helper(nums, [], result, new Array(nums.length).fill(false));
  return result;
};
function helper(nums, currentList, result, visited) {
  if (currentList.length === nums.length) {
    result.push([...currentList]);
    return;
  }
  for (let i = 0; i < nums.length; ++i) {
    if (!visited[i] && (i === 0 || nums[i - 1] !== nums[i] || visited[i - 1])) {
      currentList.push(nums[i]);
      visited[i] = true;

      helper(nums, currentList, result, visited);

      currentList.pop();
      visited[i] = false;
    }
  }
}

Python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        self.helper(nums, [], result, [False] * len(nums))
        return result

    def helper(self, nums: List[int], currentList: List[int], result: List[List[int]], visited: List[bool]) -> None:
        if len(currentList) == len(nums):
            result.append(currentList.copy())
            return
        for i in range(len(nums)):
            if not visited[i] and (i == 0 or nums[i - 1] != nums[i] or visited[i - 1]):
                currentList.append(nums[i])
                visited[i] = True
                self.helper(nums, currentList, result, visited)
                currentList.pop()
                visited[i] = False

C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        vector<int> currentList;
        vector<bool> visited(nums.size(), false);
        helper(nums, currentList, result, visited);
        return result;
    }
private:
    void helper(const vector<int>& nums, vector<int> currentList, vector<vector<int>>& result, vector<bool>& visited) {
        if (currentList.size() == nums.size()) {
            result.push_back(currentList);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (!visited[i] && (i == 0 || nums[i - 1] != nums[i] || visited[i - 1])) {
                currentList.push_back(nums[i]);
                visited[i] = true;

                helper(nums, currentList, result, visited);

                currentList.pop_back();
                visited[i] = false;
            }
        }
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n*n!)
• Space Complexity: O(n)

---

Explanation:

Combining the ideas from Permutations and from Subsets II we can easily get to this solution. Note is almost identical to the permutations where input array has no duplicates, but now we use the techniques explained in the subsets of input array with duplicates. So, we sort the input array and then only choose element if it wasn’t visited yet and it fulfills either one of the following requirements:

• it's the first element to choose
• it's different than the previous element
• it's the same as the previous element, but the previous element has also been chosen.

The rest of the solution follows the same logic as we had Permutations with the same time and space complexity.