medium Permutations II

Problem Statement

Given a list of numbers nums that might have duplicates, return all unique arrangements of the numbers in any order.

Examples

Example 1:

• Input: nums = [1, 2, 2]
• Output: [[1,2,2],[2,1,2],[2,2,1]]
• Explanation: There are a total of 6 permutations of [1, 2, 2] list but only 3 are unique.

Example 2:

• Input: nums = [2, 2, 3]
• Output: [[2,2,3],[2,3,2],[3,2,2]]
• Explanation: All unique permutations of the list [2, 2, 3] are shown above.

Example 3:

• Input: nums = [1, 2, 2, 3]
• Output: [[1,2,2,3],[1,2,3,2],[1,3,2,2],[2,1,2,3],[2,1,3,2],[2,2,1,3],[2,2,3,1],[2,3,1,2],[2,3,2,1],[3,1,2,2],[3,2,1,2],[3,2,2,1]]
• Explanation: All unique permutations of the list [1, 2, 2, 3] are shown above.

Constraints:

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

Solution

To solve this problem, we need to generate all possible permutations of the input list while ensuring that we do not include duplicate permutations. We can achieve this by sorting the list first, which helps in skipping duplicate numbers during the permutation process. Using a backtracking approach, we build permutations incrementally by adding one number at a time and ensuring that each number is not used more than once at a specific position. By marking numbers that have been used in the current recursive call, we can avoid duplicates effectively.

This approach works well because it systematically explores all potential permutations while skipping over duplicate entries. By leveraging a sorted list and a used array, we ensure each permutation is unique and all possible permutations are considered.

Step-by-Step Algorithm

1. Sort the input array nums to handle duplicates easily.
2. Initialize an empty list result to store all unique permutations.
3. Define a helper function backtrack that takes the current permutation tempList, a boolean array used to track used elements, and nums.
4. Check if the length of tempList is equal to the length of nums:
   • If true, add a copy of tempList to result.
   • If false, proceed to the next step.
5. Iterate over each element in nums:
   • Skip elements that are already used or duplicate elements that are not used in the current recursive call.
   • Mark the current element as used.
   • Add the current element to tempList.
   • Recursively call backtrack with the updated tempList and used array.
   • Backtrack by unmarking the current element and removing it from tempList.
6. Call the backtrack function with an empty tempList and a used array of False values.
7. Return the result list containing all unique permutations.

Algorithm Walkthrough

Using the input nums = [1, 2, 2]:

1. Sort the array: The sorted array remains [1, 2, 2].
2. Initialize result: result = [].
3. Call backtrack with tempList = [] and used = [False, False, False].

First Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, not used. Add to tempList and mark as used.
     • tempList = [1], used = [True, False, False].
     • Call backtrack with updated tempList and used.

Second Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, already used. Skip.
   • i = 1:
     • nums[1] = 2, not used. Add to tempList and mark as used.
     • tempList = [1, 2], used = [True, True, False].
     • Call backtrack with updated tempList and used.

Third Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, already used. Skip.
   • i = 1:
     • nums[1] = 2, already used. Skip.
   • i = 2:
     • nums[2] = 2, not used. Add to tempList and mark as used.
     • tempList = [1, 2, 2], used = [True, True, True].
     • Call backtrack with updated tempList and used.

Fourth Level:

1. tempList length equals nums length.
   • Add [1, 2, 2] to result.
   • result = [[1, 2, 2]].

Backtrack:

1. Unmark nums[2] and remove from tempList.
   • tempList = [1, 2], used = [True, True, False].
2. Return to the previous level.

Backtrack:

1. Unmark nums[1] and remove from tempList.
   • tempList = [1, 2], used = [True, False, True].
2. Return to the previous level.

Third Level:

1. Continue iteration:
   • i = 2:
     • Already processed. Skip.

Backtrack:

1. Unmark nums[2] and remove from tempList.
   • tempList = [1], used = [True, False, False].
2. Return to the previous level.

First Level:

1. Continue iteration:
   • i = 1:
     • nums[1] = 2, not used. Add to tempList and mark as used.
     • tempList = [2], used = [False, True, False].
     • Call backtrack with updated tempList and used.

Second Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, not used. Add to tempList and mark as used.
     • tempList = [2, 1], used = [True, True, False].
     • Call backtrack with updated tempList and used.

Third Level:

1. Iterate over nums:
   • i = 0:
     • Already used. Skip.
   • i = 1:
     • Already used. Skip.
   • i = 2:
     • nums[2] = 2, not used. Add to tempList and mark as used.
     • tempList = [2, 1, 2], used = [True, True, True].
     • Call backtrack with updated tempList and used.

Fourth Level:

1. tempList length equals nums length.
   • Add [2, 1, 2] to result.
   • result = [[1, 2, 2], [2, 1, 2]].

Backtrack:

1. Unmark nums[2] and remove from tempList.
   • tempList = [2, 1], used = [True, True, False].
2. Return to the previous level.

Third Level:

1. Continue iteration:
   • i = 2:
     • Already processed. Skip.

Backtrack:

1. Unmark nums[0] and remove from tempList.
   • tempList = [2], used = [False, True, False].
2. Return to the previous level.

Second Level:

1. Continue iteration:
   • i = 1:
     • Already processed. Skip.
   • i = 2:
     • nums[2] = 2, not used. Add to tempList and mark as used.
     • tempList = [2, 2], used = [False, True, True].
     • Call backtrack with updated tempList and used.

Third Level:

1. Iterate over nums:
   • i = 0:
     • nums[0] = 1, not used. Add to tempList and mark as used.
     • tempList = [2, 2, 1], used = [True, True, True].
     • Call backtrack with updated tempList and used.

Fourth Level:

1. tempList length equals nums length.
   • Add [2, 2, 1] to result.
   • result = [[1, 2, 2], [2, 1, 2], [2, 2, 1]].

Return Result:

• All permutations of the [1, 2, 2] list are [[1, 2, 2], [2, 1, 2], [2, 2, 1]].

Code

import java.util.*;

public class Solution {

  // Method to return all unique permutations
  public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums); // Sort the numbers to handle duplicates
    backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
  }

  // Helper method for backtracking
  private void backtrack(
    List<List<Integer>> result,
    List<Integer> tempList,
    int[] nums,
    boolean[] used
  ) {
    if (tempList.size() == nums.length) {
      result.add(new ArrayList<>(tempList)); // Add the current permutation to the result
    } else {
      for (int i = 0; i < nums.length; i++) {
        if (
          used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
        ) continue; // Skip duplicates
        used[i] = true; // Mark the number as used
        tempList.add(nums[i]); // Add number to the current permutation
        backtrack(result, tempList, nums, used); // Recur with the next number
        used[i] = false; // Unmark the number
        tempList.remove(tempList.size() - 1); // Remove the number from the current permutation
      }
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[][] inputs = { { 1, 2, 2 }, { 2, 2, 3 }, { 1, 2, 2, 3 } };
    for (int[] input : inputs) {
      List<List<Integer>> result = sol.permuteUnique(input);
      System.out.println("Input: " + Arrays.toString(input));
      System.out.println("Permutations: " + result);
    }
  }
}

Complexity Analysis

Time Complexity

The time complexity of generating all permutations is , where n is the length of the input array. This is because:

• There are n! permutations in total.
• For each permutation, it takes time to build and store it.

Additionally, sorting the array initially takes time. However, this sorting step is dominated by the permutation generation, making the overall time complexity .

Space Complexity

The space complexity is because:

• We store all n! permutations, each of length n.
• The recursion stack can go as deep as n, and we maintain a temporary list of length n and a used array of length n.

Hence, the overall space complexity is .