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.
Flowchart Walkthrough
To determine the appropriate solving pattern for Leetcode 47. Permutations II, let's follow the decisions laid out in the Flowchart:
Is it a graph?
- No: The problem is about generating permutations, not graph traversal.
Need to solve for kth smallest/largest?
- No: The problem task is to generate unique permutations, not to find specific order statistics.
Involves Linked Lists?
- No: The problem involves arrays or lists, not linked lists specifically.
Does the problem have small constraints?
- Yes: The input size for permutations problems is typically small enough to manage due to the factorial growth of the output size.
Brute force / Backtracking?
- Yes: Generating all permutations, especially with duplicate values involved, requires backtracking to handle uniqueness and efficient exploration of all candidate permutations.
Conclusion: Following the flowchart leads to the backtracking approach as the ideal method for generating all unique permutations of the array, taking special care to account for duplicates.
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:
-
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. -
Prepare Helper Structures: We create a helper array
t
to store the current permutation and avis
array to keep track of whether an element at a given index has been used in the current permutation or not. -
Define a DFS Helper Function: We define a recursive function
dfs(i)
wherei
is the current index in thet
array that we are trying to fill. This function will try to fillt[i]
with every possible number from thenums
array that hasn't been used yet (as indicated by thevis
array). -
Recursion and Backtracking: The
dfs
function iterates throughnums
. For each number at indexj
:- If
vis[j]
isTrue
(the number has been used already), skip it. - If
nums[j]
is equal tonums[j - 1]
andvis[j - 1]
isFalse
(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 settingt[i]
tonums[j]
, markingvis[j]
asTrue
, and recursively callingdfs(i + 1)
.
- If
-
Save and Reset on Backtracking: Whenever we reach the base case of
dfs
, which is wheni == n
, it means we have filled up thet
array with a valid permutation. We add a copy oft
to the answer listans
. Then, we backtrack by resetting thevis[j]
toFalse
, essentially marking the number at indexj
as unused and available for future permutations. -
Invoke and Return: We kickstart the DFS by calling
dfs(0)
. After the recursive calls are done, all unique permutations are stored inans
, which we then return.
By following this approach, we effectively avoid constructing duplicate permutations and generate all unique permutations in an efficient manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example where nums = [1, 1, 2]
to illustrate this approach.
-
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. -
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.
- We create an array
-
Define a DFS Helper Function: We define a recursive function
dfs(i)
, wherei
denotes the number of elements in the current permutation. This function attempts to generate all unique permutations by trying to fillt
with elements fromnums
. -
Recursion and Backtracking:
- Start the first recusive call
dfs(0)
. Here, we attempt to pick the first element (i=0
) for our permutationt
. - The
dfs
function iterates through the indices ofnums
([0, 1, 2]
in our example). - For each
j
in[0, 1, 2]
:- On the first iteration
j=0
, sincevis[0]
isFalse
, we can picknums[0]
to be part of the permutation. Sot[0]
becomes1
, andvis[0]
becomesTrue
. We calldfs(1)
to pick the next element fort
. - Inside
dfs(1)
, we cannot picknums[1]
because it would be a duplicate (nums[1]
is equal tonums[0]
andvis[0]
is nowTrue
). We skip and proceed toj=2
. - We pick
nums[2]
, sot[1]
becomes2
, andvis[2]
becomesTrue
. We calldfs(2)
to pick the last element fort
. - Inside
dfs(2)
, we only have one choice left, which isnums[1]
sincevis[1]
isFalse
. We sett[2]
to1
, and nowt = [1, 2, 1]
. We reached the base case becausei
equalsn (3)
ā the length ofnums
. We add[1, 2, 1]
toans
. - Now we backtrack. We reset
vis[1]
toFalse
and go up todfs(1)
. - In
dfs(1)
, we backtrack again by resettingvis[2]
toFalse
and return todfs(0)
. - Now
j=1
is the current index indfs(0)
, and sincenums[1]
is a duplicate with an unused previous element (nums[0]
), it is skipped. - We proceed with
j=2
, by settingt[0]
to2
,vis[2]
toTrue
, and calldfs(1)
. - In
dfs(1)
, now we can usenums[0]
andnums[1]
becausenums[0]
is not a duplicate in the current context oft
. We create permutations[2, 1, 1]
in a similar way and add them toans
.
- On the first iteration
- Start the first recusive call
-
Save and Reset on Backtracking: Each time we hit the base case (
i == n
), we have a complete permutation to add toans
. We then backtrack, undoing the last step in our permutation to free up elements for new permutations. -
Invoke and Return: We start by invoking
dfs(0)
, and after all the recursive calls and backtracks, we getans = [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
, which are all the unique permutations ofnums
.
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 storeN!
permutations, each of sizeN
in the case of all unique elements, soO(N!*N)
space complexity for storing the output.- Temporary array
t
of sizeN
, andvis
array also of sizeN
, giveO(N)
. - The maximum depth of the recursion stack is
N
, leading toO(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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!