46. Permutations

MediumArrayBacktracking
Leetcode Link

Problem Description

Given an array nums of distinct integers, the goal is to find all the possible permutations of these integers. A permutation is a rearrangement of the elements in an array in a different order. Since the array contains distinct integers, each permutation will also contain all the elements of the original array but in a different sequence. The result can be returned in any order, meaning that there is no need to sort or arrange the permutations in a particular sequence. The goal is to list all distinct ways the elements can be ordered.

Intuition

The intuition behind the solution is to use Depth-First Search (DFS). DFS is a common algorithm for traversing or searching tree or graph data structures. The idea is to follow one branch of the tree down as many levels as possible until the end is reached, and then proceed to the next branch.

When dealing with permutations, we can imagine each permutation as a path in a decision tree, where each level represents an element in the permutation and each branch represents a choice of which element to place next.

Here's how we can visualize this approach:

  1. Start with an empty permutation.
  2. For every index in the permutation, try placing each unused element (one that has not been used in this particular path/branch).
  3. After an element is placed at the current index, mark it as used and move to the next index.
  4. Once an index is placed with all possible elements, backtrack (step back) and try the next possible element for the previous index.
  5. Repeat until all elements are placed in the permutation, meaning we've reached the end of the branch. This permutation is then added to the list of results.
  6. When all branches are explored, we will have found all the permutations.

The dfs() function is a recursive method that implements this approach. It uses the index i to keep track of the depth of recursion (which corresponds to the current position in the permutation). The vis array helps track which elements have been used, and the t array represents the current permutation being constructed. Once index i reaches n, the length of nums, it means a full permutation has been created and it's added to the answer ans.

To sum up, the problem is solved by systematically exploring all possible placements of elements using DFS, while making sure to backtrack at the appropriate times, hence constructing all unique permutations.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The solution uses a classic Depth-First Search (DFS) algorithm implemented through recursion to explore all potential permutations in a systematic way. The key to the DFS algorithm in this context is to treat each level of recursion as a position in the permutation, and to attempt to fill that position with each possible unused element from the nums array.

Here's a step-by-step breakdown of the algorithm:

  1. Initialize an n-length boolean array vis to keep track of which elements from nums have been used in the current branch of the DFS. At first, all values are False indicating no elements have been used yet.

  2. Create a temporary array t of length n. This array will hold the current permutation as it is being built.

  3. An empty list ans is initialized to store all the completed permutations.

  4. The dfs function is defined to perform the DFS. It takes an argument i which is the current depth of the DFS, corresponding to the index in the permutation where we are placing the next element.

  5. In the dfs function, the base condition checks if i is equal to n. If true, it means we've reached the end of a branch in the DFS and a full permutation has been constructed, so we append a copy of this permutation to ans.

  6. If the base condition is not met, the function proceeds to iterate over all elements of nums.

    • For each element, if it has not already been used (i.e., vis[j] is False), we mark it as used by setting vis[j] to True.
    • We then place this element in the i-th position of the current permutation being built t[i].
    • Call dfs(i + 1) to proceed to the next level of depth, attempting to find an element for the next position.
    • After returning from the deeper recursive call, we reset vis[j] to False to "unchoose" the element, thus enabling it to be used in a different branch or permutation. This is the backtracking step.

  7. The initial call to dfs is made with an argument of 0 to start the DFS from the first position in the permutation.

  8. Finally, the ans list is returned which now contains all possible permutations.

This approach uses a combination of recursive DFS for the traversal mechanism, backtracking for generating permutations without duplicates, and dynamic data structures to keep track of the used elements and current permutations. The elegance of this solution lies in how it natively handles the permutations' creation without redundancy, which is essential in problems where the order of elements matters and you want to consider all possible orderings.

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

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's illustrate the solution approach using a simple example where our array nums is [1,2,3]. We want to find all permutations of this array.

  1. We initialize a boolean array vis of length 3 (n=3 in this case), all set to False, which will help us keep track of the elements that have been used in the current permutation. We also create a temporary array t to build the current permutation and an empty list ans to store all permutations.

    vis = [False, False, False] t = [0, 0, 0] ans = []

  2. Start the DFS with dfs(i=0). At this level of recursion, we are looking to fill in the first position of the t array.

  3. Our for loop in the dfs function will consider each element in nums: a. On the first iteration, we choose 1. We set vis[0] to True and place 1 in t[0]. b. We call dfs(i=1) to decide on the second element of the permutation.

  4. Now we are in a new level of recursion, trying to fill t[1]. Again, we traverse nums. We skip 1 because vis[0] is True. We pick 2, set vis[1] to True, and place 2 in t[1]. a. We call dfs(i=2).

  5. The next level of recursion is to place the third element. 1 and 2 are marked as used, so we pick 3, set vis[2] to True, and place 3 in t[2].

  6. Now, i equals to n. We've reached the end of the branch and have a complete permutation [1,2,3], which we add to ans.

  7. We backtrack by returning to where we picked 3. We unmark vis[2] (vis[2]=False), trying to explore other possibilities for this position, but there are no more elements left to use. So, we backtrack further.

  8. Back at the second element decision step (dfs(i=1)), we backtrack off of element 2 and pick 3 for t[1]. vis is now [True, False, True]. We call dfs(i=2) to decide the third element.

  9. In this call, 2 is the only unused element, so we put it in t[2], making the permutation [1,3,2]. We add this to ans.

This recursive process continues, systematically exploring each possible permutation and backtracking after exploring each branch to the fullest extent. This ensures that we explore all permutations without duplication.

In the end, ans would be:

1ans = [
2    [1, 2, 3],
3    [1, 3, 2],
4    [2, 1, 3],
5    [2, 3, 1],
6    [3, 1, 2],
7    [3, 2, 1]
8]

This walk through represents how the algorithm builds up permutations and how it builds the result step by step.

Solution Implementation

1class Solution:
2    def permute(self, nums: List[int]) -> List[List[int]]:
3        # Helper function to perform depth-first search for permutation generation
4        def backtrack(index):
5            # If the current index has reached the length of nums list,
6            # we have a complete permutation
7            if index == len_nums:
8                permutations.append(current_permutation[:])
9                return
10          
11            # Iterate over the nums list to create permutations
12            for j in range(len_nums):
13                # Check if the number at index j is already used in the current permutation
14                if not visited[j]:
15                    # If not visited, mark it as visited and add to current permutation
16                    visited[j] = True
17                    current_permutation[index] = nums[j]
18                    # Recurse with next index
19                    backtrack(index + 1)
20                    # Backtrack: unmark the number at index j as visited for the next iteration
21                    visited[j] = False
22
23        len_nums = len(nums)  # Store the length of the input list
24        visited = [False] * len_nums  # Create a visited list to track numbers that are used
25        current_permutation = [0] * len_nums  # Temp list to store the current permutation
26        permutations = []  # Result list to store all the permutations
27        backtrack(0)  # Start generating permutations from index 0
28        return permutations
29
1class Solution {
2    // List to hold all the permutations
3    private List<List<Integer>> permutations = new ArrayList<>();
4  
5    // Temporary list to hold the current permutation
6    private List<Integer> currentPermutation = new ArrayList<>();
7  
8    // Visited array to keep track of the elements already included in the permutation
9    private boolean[] visited;
10  
11    // Array of numbers to create permutations from
12    private int[] elements;
13
14    // Method to initiate the process of finding all permutations
15    public List<List<Integer>> permute(int[] nums) {
16        elements = nums;
17        visited = new boolean[nums.length];
18        backtrack(0);
19        return permutations;
20    }
21
22    // Helper method to perform backtracking
23    private void backtrack(int index) {
24        // Base case: if the permutation size is equal to the number of elements, add it to the answer
25        if (index == elements.length) {
26            permutations.add(new ArrayList<>(currentPermutation));
27            return;
28        }
29      
30        // Iterate through the elements array
31        for (int j = 0; j < elements.length; ++j) {
32            // If the element at index j has not been visited, include it in the permutation
33            if (!visited[j]) {
34                // Mark the element at index j as visited
35                visited[j] = true;
36                // Add the element to the current permutation
37                currentPermutation.add(elements[j]);
38                // Continue to the next level of depth (next index)
39                backtrack(index + 1);
40                // Backtrack: remove the last element added and mark it as not visited
41                currentPermutation.remove(currentPermutation.size() - 1);
42                visited[j] = false;
43            }
44        }
45    }
46}
47
1#include <vector>
2#include <functional> // For the std::function
3
4class Solution {
5public:
6    // Function to generate all permutations of the input vector of integers.
7    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
8        int n = nums.size(); // Get the size of the nums vector.
9        std::vector<std::vector<int>> permutations; // To store all permutations.
10        std::vector<int> current_permutation(n); // Current permutation vector.
11        std::vector<bool> visited(n, false); // Visited flags for nums elements.
12
13        // Recursive Depth-First Search (DFS) function to generate permutations.
14        std::function<void(int)> dfs = [&](int depth) {
15            if (depth == n) { // Base case: if the current permutation is complete.
16                permutations.emplace_back(current_permutation); // Add to permutations.
17                return; // End of branch.
18            }
19            for (int i = 0; i < n; ++i) { // Iterate through nums elements.
20                if (!visited[i]) { // If the ith element has not been visited.
21                    visited[i] = true; // Mark as visited.
22                    current_permutation[depth] = nums[i]; // Set in current permutation.
23
24                    dfs(depth + 1); // Recurse with the next depth.
25
26                    visited[i] = false; // Unmark as visited for backtracking.
27                }
28            }
29        };
30
31        dfs(0); // Start the DFS with depth 0.
32        return permutations; // Return all the generated permutations.
33    }
34};
35
1// Function to generate all permutations of an array of numbers
2function permute(nums: number[]): number[][] {
3    const n = nums.length; // Length of the array to permute
4    const results: number[][] = []; // Results array that will hold all permutations
5
6    // Helper function 'depthFirstSearch' to explore the permutations using DFS strategy
7    const depthFirstSearch = (currentIndex: number) => {
8        // If the current index reaches the end of array, record the permutation
9        if (currentIndex === n) {
10            results.push([...nums]); // Add a copy of the current permutation
11            return;
12        }
13
14        // Iterate over the array to swap each element with the element at 'currentIndex'
15        for (let swapIndex = currentIndex; swapIndex < n; swapIndex++) {
16            // Swap the elements
17            [nums[currentIndex], nums[swapIndex]] = [nums[swapIndex], nums[currentIndex]];
18            // Recursively call 'depthFirstSearch' with the next index
19            depthFirstSearch(currentIndex + 1);
20            // Swap back the elements to revert to the original array before the next iteration
21            [nums[currentIndex], nums[swapIndex]] = [nums[swapIndex], nums[currentIndex]];
22        }
23    };
24
25    // Initiate depth-first search starting from index 0
26    depthFirstSearch(0);
27    // Return all generated permutations
28    return results;
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

Time and Space Complexity

The provided Python code generates all permutations of a list of integers, using a backtracking algorithm.

Time Complexity

The time complexity of the algorithm is determined by the number of recursive calls made, and the work done in each call. The function dfs is called recursively until it reaches the base case (i == n).

For n distinct elements, there are n! (factorial of n) permutations. At each level of the recursion, we make n choices, then n - 1 for the next level, and so on, which means we are doing n! work as there are that many permutations to generate and for each of them we do O(1) operation. Hence, the time complexity is O(n!).

Space Complexity

The space complexity consists of the space used by the recursive call stack and the space used to maintain the state (visited array vis and temporary list t).

  1. Recursive Call Stack: Since the depth of the recursion is n, at most O(n) functions will be placed on the call stack simultaneously.
  2. State Maintenance: The list vis and t require O(n) space each.

The total space complexity, therefore, is O(n) + O(n) * O(2) = O(n). However, since O(2) is a constant factor, it simplifies to O(n).

Taking all this into account, the space complexity is O(n) for maintaining the auxiliary data structure and the recursive call stack depth.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Backtracking 1

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching 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.

←
↑TA 👨‍🏫