47. Permutations II


Problem Description

The problem requires us to generate all possible unique permutations of a given collection of numbers nums. The nums array may contain duplicates, which adds a layer of complexity because we have to ensure that our permutations are unique and do not include the same sets of numbers more than once. The challenge is to come up with a way that efficiently explores all potential combinations without revisiting the same permutations.

Intuition

The intuition behind the solution is to use Depth-First Search (DFS) in combination with backtracking to explore all possible orderings of numbers. However, since we have potential duplicates in the array, we have to be very cautious about how we recurse.

Firstly, sorting the nums array helps bring duplicate elements next to each other, which is crucial for our later steps to detect and skip duplicates efficiently.

Then, we use a vis array of boolean values to keep track of which elements have been used in the current permutation. This is to avoid reusing elements unintentionally, as each number must appear exactly once in any permutation.

While we are constructing permutations, we need to handle the possibility of duplicates. We incorporate a condition to skip over a number if it is the same as the previous number and the previous number has not been included in the current permutation. This check ensures that we are not generating any duplicate permutations because it prevents the algorithm from picking the same element twice when the elements are identical and the previous one is unused.

By using recursive DFS, we explore all paths in the search space that lead to valid unique permutations. As we hit the base case where the depth (i) equals the length of the numbers array (n), we've successfully built a valid permutation and we append a copy of the current permutation (represented by array t) to our results list (ans).

This approach ensures that each permutation in the results list ans is unique and contains all elements from the nums array exactly once.

Learn more about Backtracking patterns.

Solution Approach

The solution approach is based on Depth-First Search (DFS) and backtracking. The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead if possible, else by backtracking.

Here is how we implement the solution:

  1. Sort the Array: First, we sort the nums array. Sorting is crucial because it makes the detection of duplicates easy by placing them next to each other.

  2. Prepare Helper Structures: We create a helper array t to store the current permutation and a vis array to keep track of whether an element at a given index has been used in the current permutation or not.

  3. Define a DFS Helper Function: We define a recursive function dfs(i) where i is the current index in the t array that we are trying to fill. This function will try to fill t[i] with every possible number from the nums array that hasn't been used yet (as indicated by the vis array).

  4. Recursion and Backtracking: The dfs function iterates through nums. For each number at index j:

    • If vis[j] is True (the number has been used already), skip it.
    • If nums[j] is equal to nums[j - 1] and vis[j - 1] is False (the number is a duplicate and the previous occurrence hasn't been used yet), skip it to prevent a duplicate permutation.
    • Otherwise, choose nums[j] by setting t[i] to nums[j], marking vis[j] as True, and recursively calling dfs(i + 1).
  5. Save and Reset on Backtracking: Whenever we reach the base case of dfs, which is when i == n, it means we have filled up the t array with a valid permutation. We add a copy of t to the answer list ans. Then, we backtrack by resetting the vis[j] to False, essentially marking the number at index j as unused and available for future permutations.

  6. Invoke and Return: We kickstart the DFS by calling dfs(0). After the recursive calls are done, all unique permutations are stored in ans, which we then return.

By following this approach, we effectively avoid constructing duplicate permutations and generate all unique permutations in an efficient manner.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's walk through an example where nums = [1, 1, 2] to illustrate this approach.

  1. Sort the Array: First of all, we sort the array nums. The array is already sorted [1, 1, 2] so no changes are made. Sorting is important to identify duplicates.

  2. Prepare Helper Structures:

    • We create an array t to store the current permutation sequence, which is initially empty.
    • An array vis is created to keep track if an element has been added to the current permutation. Initially, vis = [False, False, False] because no numbers have been used yet.
  3. Define a DFS Helper Function: We define a recursive function dfs(i), where i denotes the number of elements in the current permutation. This function attempts to generate all unique permutations by trying to fill t with elements from nums.

  4. Recursion and Backtracking:

    • Start the first recusive call dfs(0). Here, we attempt to pick the first element (i=0) for our permutation t.
    • The dfs function iterates through the indices of nums ([0, 1, 2] in our example).
    • For each j in [0, 1, 2]:
      • On the first iteration j=0, since vis[0] is False, we can pick nums[0] to be part of the permutation. So t[0] becomes 1, and vis[0] becomes True. We call dfs(1) to pick the next element for t.
      • Inside dfs(1), we cannot pick nums[1] because it would be a duplicate (nums[1] is equal to nums[0] and vis[0] is now True). We skip and proceed to j=2.
      • We pick nums[2], so t[1] becomes 2, and vis[2] becomes True. We call dfs(2) to pick the last element for t.
      • Inside dfs(2), we only have one choice left, which is nums[1] since vis[1] is False. We set t[2] to 1, and now t = [1, 2, 1]. We reached the base case because i equals n (3) – the length of nums. We add [1, 2, 1] to ans.
      • Now we backtrack. We reset vis[1] to False and go up to dfs(1).
      • In dfs(1), we backtrack again by resetting vis[2] to False and return to dfs(0).
      • Now j=1 is the current index in dfs(0), and since nums[1] is a duplicate with an unused previous element (nums[0]), it is skipped.
      • We proceed with j=2, by setting t[0] to 2, vis[2] to True, and call dfs(1).
      • In dfs(1), now we can use nums[0] and nums[1] because nums[0] is not a duplicate in the current context of t. We create permutations [2, 1, 1] in a similar way and add them to ans.
  5. Save and Reset on Backtracking: Each time we hit the base case (i == n), we have a complete permutation to add to ans. We then backtrack, undoing the last step in our permutation to free up elements for new permutations.

  6. Invoke and Return: We start by invoking dfs(0), and after all the recursive calls and backtracks, we get ans = [[1, 1, 2], [1, 2, 1], [2, 1, 1]], which are all the unique permutations of nums.

By following this ordered approach, we have now generated all valid unique permutations of nums by ensuring we don't produce any repetition arising from duplicates.

Solution Implementation

1class Solution:
2    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
3        # Helper function to perform depth-first search (DFS) to find unique permutations
4        def backtrack(index: int):
5            # If the current index is equal to the size of nums, we have a complete permutation to add to the answer
6            if index == size:
7                permutations.append(current_permutation[:])
8                return
9          
10            # Iterate through each number trying to construct the next permutation
11            for j in range(size):
12                # Skip this number if it has been used already or if it's a duplicate and its previous instance was not used
13                if visited[j] or (j > 0 and nums[j] == nums[j - 1] and not visited[j - 1]):
14                    continue
15              
16                # Choose the number nums[j] and mark it as visited
17                current_permutation[index] = nums[j]
18                visited[j] = True
19              
20                # Recur to construct the next index's permutation
21                backtrack(index + 1)
22              
23                # Unchoose the number nums[j] and mark it as unvisited for further iterations
24                visited[j] = False
25
26        size = len(nums)
27        nums.sort()  # Sort nums to handle duplicates
28        permutations = []  # This will hold all unique permutations
29        current_permutation = [0] * size  # Temporary list to hold a single permutation
30        visited = [False] * size  # List to keep track of visited indices in nums
31      
32        # Start the DFS from index 0
33        backtrack(0)
34      
35        return permutations  # Return all the collected permutations
36
1class Solution {
2    // List to store all unique permutations
3    private List<List<Integer>> permutations = new ArrayList<>();
4    // Temporary list to store one permutation
5    private List<Integer> tempPermutation = new ArrayList<>();
6    // Array of numbers to create permutations from
7    private int[] numbers;
8    // Visited flags to track whether a number has been used in the current permutation
9    private boolean[] visited;
10
11    public List<List<Integer>> permuteUnique(int[] nums) {
12        // Sort the numbers to ensure duplicates are adjacent
13        Arrays.sort(nums);
14        // Initialize class variables
15        this.numbers = nums;
16        visited = new boolean[nums.length];
17        // Start the depth-first search from the first index
18        dfs(0);
19        // Return the list of all unique permutations found
20        return permutations;
21    }
22
23    private void dfs(int index) {
24        // Base case: If the current permutation is complete, add it to the list of permutations
25        if (index == numbers.length) {
26            permutations.add(new ArrayList<>(tempPermutation));
27            return;
28        }
29        // Iterate over the numbers to build all possible permutations
30        for (int i = 0; i < numbers.length; ++i) {
31            // Skip the current number if it's already been used or if it's a duplicate and the duplicate hasn't been used
32            if (visited[i] || (i > 0 && numbers[i] == numbers[i - 1] && !visited[i - 1])) {
33                continue;
34            }
35            // Add the current number to the current permutation and mark it as visited
36            tempPermutation.add(numbers[i]);
37            visited[i] = true;
38            // Recursively continue building the permutation
39            dfs(index + 1);
40            // Backtrack by removing the current number and unmarking it as visited
41            visited[i] = false;
42            tempPermutation.remove(tempPermutation.size() - 1);
43        }
44    }
45}
46
1class Solution {
2public:
3    // Function to generate all unique permutations of vector 'nums'.
4    vector<vector<int>> permuteUnique(vector<int>& nums) {
5        // First, sort the array to handle duplicates.
6        sort(nums.begin(), nums.end());
7        // Get the size of the nums vector.
8        int size = nums.size();
9        // This will hold all the unique permutations.
10        vector<vector<int>> permutations;
11        // Temporary vector to hold current permutation.
12        vector<int> current(size);
13        // Visited array to keep track of used elements.
14        vector<bool> visited(size, false);
15
16        // Recursive lambda function to perform Depth-First Search.
17        function<void(int)> dfs = [&](int depth) {
18            // If the current permutation is complete, add to permutations.
19            if (depth == size) {
20                permutations.emplace_back(current);
21                return;
22            }
23            // Iterate over all elements in 'nums'.
24            for (int i = 0; i < size; ++i) {
25                // Skip already visited elements or duplicates not in sequence.
26                if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
27                    continue;
28                }
29                // Place nums[i] in the current position.
30                current[depth] = nums[i];
31                // Mark this element as visited.
32                visited[i] = true;
33                // Recurse with next position.
34                dfs(depth + 1);
35                // Reset visited status for backtracking.
36                visited[i] = false;
37            }
38        };
39        // Start the recursive process with the first position.
40        dfs(0);
41        // Return the resulting permutations.
42        return permutations;
43    }
44};
45
1// Given an array of numbers, this function returns all unique permutations
2function permuteUnique(nums: number[]): number[][] {
3    // Sort the input array
4    nums.sort((a, b) => a - b);
5
6    // Define the length of the nums array
7    const length = nums.length;
8
9    // This array will store all the unique permutations
10    const results: number[][] = [];
11
12    // Temporary array to store one permutation at a time
13    const permutation: number[] = new Array(length);
14
15    // Visited array to keep track of which elements are used
16    const visited: boolean[] = new Array(length).fill(false);
17
18    // Helper function to generate permutations using DFS (Depth-First Search)
19    const dfs = (index: number) => {
20        // If the temporary array is filled, add a copy to results
21        if (index === length) {
22            results.push([...permutation]);
23            return;
24        }
25
26        for (let j = 0; j < length; ++j) {
27            // Skip already visited elements or duplicates (to ensure uniqueness)
28            if (visited[j] || (j > 0 && nums[j] === nums[j - 1] && !visited[j - 1])) {
29                continue;
30            }
31
32            // Choose the element and mark as visited
33            permutation[index] = nums[j];
34            visited[j] = true;
35
36            // Continue building the permutation
37            dfs(index + 1);
38
39            // Backtrack: unmark the element after recursive call returns
40            visited[j] = false;
41        }
42    };
43
44    // Start the DFS traversal from the first index
45    dfs(0);
46
47    // Return all the unique permutations
48    return results;
49}
50

Time and Space Complexity

The given Python code implements a backtracking algorithm to generate all unique permutations of a list of numbers.

Time Complexity

The time complexity of the algorithm is mainly influenced by the number of recursive calls (dfs function) made to construct the permutations. The sorting operation at the start has a time complexity of O(N log N), where N is the number of elements in nums.

In the worst case (when all elements are unique), the number of unique permutations is N! (factorial of N). However, due to the branch pruning by checking vis[j] and the uniqueness condition (j and nums[j] == nums[j - 1] and not vis[j - 1]), the actual number of permutations explored is less than N!. This optimization is significant especially when nums contains many duplicates.

However, it's hard to define a precise time complexity in the presence of these optimizations without knowing the distribution of numbers in nums. In the worst case, we can consider the complexity to be O(N!*N), as for each permutation, there is an O(N) check due to the uniqueness conditions and assigning values to t.

Space Complexity

The space complexity is determined by the amount of memory used to store the temporary arrays and the recursion stack.

  • ans array which can potentially store N! permutations, each of size N in the case of all unique elements, so O(N!*N) space complexity for storing the output.
  • Temporary array t of size N, and vis array also of size N, give O(N).
  • The maximum depth of the recursion stack is N, leading to O(N) space complexity.

Therefore, the total space complexity would be O(N!*N) due to the space required to store the output ans. If we don't count the space required for the output, the algorithm still uses O(N) space for the t and vis arrays, plus O(N) space for the recursion stack, leading to O(N) auxiliary space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄