46. Permutations - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given an array of distinct integers nums, return all possible permutations. A permutation is a rearrangement of the elements in the array, and every permutation should be unique.

Example 1:

Input: nums = [1, 2, 3]

Output:

[
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 1, 2],
  [3, 2, 1]
]

Explanation:
All possible arrangements of the three numbers are listed.

Example 2:

Input: nums = [0, 1]
Output:
```
[
  [0, 1],
  [1, 0]
]
```

Constraints:

1 ≤ nums.length ≤ 6 (or slightly larger in some variations)
All the integers of nums are unique.

Hints

Hint 1:
Think of the problem as making a series of choices. For each position in the permutation, you need to choose an element that has not been used yet.
Hint 2:
A common strategy is to use recursion (backtracking) where you build the permutation one element at a time, and once you have a complete permutation, you add it to your results.
Hint 3:
You can also consider iterative methods (such as the next-permutation approach), but the backtracking method is more straightforward for generating all permutations.

Approach 1: Backtracking

Idea

Use recursion to build permutations step by step. At each recursive call, iterate through the available elements, choose one to add to the current permutation, and mark it as used. After adding an element, recursively build the rest of the permutation until all elements are used. Then backtrack by removing the last added element and trying the next option.

Steps

Initialize:
Create an empty list to hold the current permutation and a list (or boolean array) to track which elements are already used.
Recursive Exploration:
- For each element in nums that hasn’t been used:
  - Add the element to the current permutation.
  - Mark it as used.
  - Recursively call the function to build the permutation further.
  - Backtrack by removing the element and marking it as unused.
Base Case:
When the current permutation’s length equals nums.length, a full permutation is formed. Add a copy of it to the results.

Approach 2: Iterative Method (Using Next Permutation)

Idea

Initial Sorting:
Start with the input array sorted.
Generate Next Permutation:
Iteratively generate the next permutation in lexicographical order until no more permutations exist.
Store Each Permutation:
Add each permutation to the results.

Note: This approach requires careful handling of lexicographical ordering and is less commonly used than backtracking for generating all permutations.

Code Implementation

Python Code (Backtracking Approach)

Python3

. . . .

Java Code (Backtracking Approach)

Java

. . . .

Complexity Analysis

Time Complexity:
- There are n! permutations for an array of length n.
- Generating each permutation takes O(n) time.
- Overall: O(n * n!).
Space Complexity:
- The space required for recursion is O(n) (for the recursion stack).
- Storing the results requires O(n * n!) space.

Step-by-Step Walkthrough and Visual Example

For nums = [1, 2, 3]:

Start with an empty permutation:
- current_perm = [], used = [False, False, False].
First Level of Recursion (choose the first element):
- Choose 1 → current_perm = [1], used = [True, False, False].
Second Level of Recursion:
- From remaining elements, choose 2 → current_perm = [1, 2], used = [True, True, False].
Third Level of Recursion:
- Only remaining element is 3 → current_perm = [1, 2, 3], used = [True, True, True].
- Base case reached → add [1, 2, 3] to the result.
- Backtrack: remove 3 → current_perm = [1, 2], mark used[2] = False.
Backtrack and Explore Other Branches:
- From current_perm = [1, 2], no other option at third level → backtrack.
- Remove 2 → current_perm = [1], mark used[1] = False.
- Now, choose 3 at second level → current_perm = [1, 3], used = [True, False, True].
- Then, at third level, choose 2 → current_perm = [1, 3, 2] → add it.
Repeat Process:
- After exploring all options with 1 as the first element, backtrack to an empty permutation and then try starting with 2, then 3, generating all 6 permutations.

Common Mistakes and Edge Cases

Common Mistakes

Not Marking Elements Correctly:
Failing to mark an element as used before recursive calls (or not unmarking during backtracking) can lead to incorrect or duplicate permutations.
Modifying Shared Data Structures:
Not creating a copy of the current permutation when adding to the result may cause future modifications to affect stored results.
Off-by-One Errors:
Ensure that the base case condition correctly checks when a full permutation has been built.

Edge Cases

Single-Element Array:
For nums = [a], the only permutation is [a].
Empty Array:
If nums is empty, the only permutation is an empty list, i.e., [[]].

Variations

Permutations II:
A variation where nums may contain duplicates. In this case, you must ensure that duplicate permutations are not generated (often by sorting and skipping duplicates).
Next Permutation:
Generate the next lexicographical permutation of an array.

Subsets:
Generating all subsets (power set) of a given array.
Combination Sum:
Finding all combinations that sum up to a target, which also uses backtracking.
Letter Combinations of a Phone Number:
Similar backtracking approach but with string combinations.

46. Permutations - Detailed Explanation

Problem Statement

Hints

Approach 1: Backtracking

Idea

Steps

Approach 2: Iterative Method (Using Next Permutation)

Idea

Code Implementation

Python Code (Backtracking Approach)

Java Code (Backtracking Approach)

Complexity Analysis

Step-by-Step Walkthrough and Visual Example

Common Mistakes and Edge Cases

Common Mistakes

Edge Cases

Variations

Related Problems for Further Practice