Permutations II medium

Problem Statement

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

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

Steps

1. Sort the input array: Sorting the input array helps to easily identify and skip duplicate permutations.

2. Backtracking Algorithm: We'll use a backtracking algorithm to generate all permutations. The algorithm explores all possible arrangements by recursively placing each number in each available position.

3. Handling Duplicates: To avoid generating duplicate permutations, we'll skip numbers that have already been used in the current permutation. We achieve this using a used array which tracks if a number in its original index is already in current permutation or not.

4. Base Case: The base case of the recursion is when we've placed all numbers in the permutation. We add this permutation to the result list.

5. Recursive Step: For each number in the array, we check if it's used. If not, we mark it as used, add it to the current permutation, recursively call the function to explore further permutations, and then backtrack (remove the number and mark it as unused).

Explanation

The backtracking algorithm systematically explores all possible arrangements. Sorting the input ensures that we process numbers in a predictable order, making it easier to detect and skip duplicate permutations. The used array efficiently tracks the usage of numbers. By checking used[i] we avoid processing the same numbers multiple times during a single recursive call.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        Array.Sort(nums); //Sort for efficient duplicate handling
        List<int> currentPermutation = new List<int>();
        bool[] used = new bool[nums.Length]; //used[i] indicates if nums[i] is used

        Backtrack(nums, used, currentPermutation, result);
        return result;
    }

    private void Backtrack(int[] nums, bool[] used, List<int> currentPermutation, IList<IList<int>> result) {
        if (currentPermutation.Count == nums.Length) {
            result.Add(new List<int>(currentPermutation)); //Add a copy to avoid modification
            return;
        }

        for (int i = 0; i < nums.Length; i++) {
            //Skip if already used or a duplicate of the previous used number
            if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) {
                continue;
            }
            
            used[i] = true;
            currentPermutation.Add(nums[i]);
            Backtrack(nums, used, currentPermutation, result);
            currentPermutation.RemoveAt(currentPermutation.Count - 1); //Backtrack
            used[i] = false;
        }
    }
}

Complexity

• Time Complexity: O(N * N!), where N is the length of the input array. Generating all permutations takes O(N!) time, and for each permutation, we perform O(N) work (copying to the result list).

• Space Complexity: O(N) for the recursion stack and the currentPermutation list. The result list could also potentially use O(N * N!) space in the worst case (all unique permutations). The used array uses O(N) space.