Problem Statement
Given an array of distinct integers nums, return all the possible permutations. You can return the answer in any order.
- Note: A permutation is a rearrangement of the elements of an array.
Example Inputs
Example 1:
Problem Solution
Approach
To generate all possible permutations of the given array nums, we can use a recursive backtracking approach. The key idea is to build permutations by selecting elements one by one and ensuring that each element is used only once in each permutation.
Steps
-
Initialize:
- Create an empty array
ans to store all valid permutations.
- Create an empty array
current to build the current permutation.
- Use a
Set (or a boolean array) to keep track of elements that have already been included in the current permutation to avoid duplicates.
-
Recursive Backtracking Function (backtrack):
-
Parameters:
current: The current permutation being built.nums: The original array of numbers.
-
Base Case:
- If the length of
current equals the length of nums, it means a complete permutation has been formed. Add a copy of current to ans.
-
Recursive Case:
- Iterate through each element in
nums.
- For each element:
- Skip if Already Used: If the element is already in
current (tracked using the Set), skip it to avoid duplicates.
- Include the Element:
- Add the element to
current.
- Mark the element as used by adding it to the
Set.
- Recursively call
backtrack to continue building the permutation.
- Remove the last element from
current (backtrack) and unmark it in the Set to explore other possibilities.
-
Start Backtracking:
- Call the
backtrack function with an empty current array.
-
Return the Result:
- After exploring all possible permutations, return the
ans array containing all valid permutations.
Code Snippet
Dry Run
Let's perform a dry run with nums = [1, 2].
-
Initial Call: backtrack()
-
First Level:
- i = 0: Number = 1
- Include 1:
current = [1]
- Mark 1 as used:
used = {1}
- Recurse:
backtrack()
-
Second Level:
- i = 0: Number = 1
- i = 1: Number = 2
- Include 2:
current = [1, 2]
- Mark 2 as used:
used = {1, 2}
- Recurse:
backtrack()
-
Third Level (Base Case Reached):
current.length === nums.length (2 === 2)- Add
[1, 2] to ans: ans = [[1, 2]]
- Backtrack: Remove 2,
current = [1], used = {1}
-
Back to Second Level:
- All elements processed.
- Backtrack: Remove 1,
current = [], used = {}
-
First Level (continued):
- i = 1: Number = 2
- Include 2:
current = [2]
- Mark 2 as used:
used = {2}
- Recurse:
backtrack()
-
Second Level:
- i = 0: Number = 1
- Include 1:
current = [2, 1]
- Mark 1 as used:
used = {1, 2}
- Recurse:
backtrack()
-
Third Level (Base Case Reached):
current.length === nums.length (2 === 2)- Add
[2, 1] to ans: ans = [[1, 2], [2, 1]]
- Backtrack: Remove 1,
current = [2], used = {2}
-
Back to Second Level:
- i = 1: Number = 2
- Backtrack: Remove 2,
current = [], used = {}
-
Final Result: [[1, 2], [2, 1]]
Complexity Analysis
Optimized Time and Space
- Time Complexity: O(n!), where
n is the number of elements in nums.
- This is because there are
n! possible permutations of n distinct numbers.
- Space Complexity: O(n)
- The space used by the recursion stack is proportional to the depth of the recursion, which is
n.
- Additionally, the
current array holds up to n elements.
Optimizations:
-
Using a Set for Tracking Used Elements: Utilizing a Set to track used elements ensures that each element is used only once in the current permutation, preventing duplicates and reducing unnecessary recursive calls.
-
Early Pruning: Since all elements are distinct, there's no need for additional checks to handle duplicates, allowing the algorithm to proceed without extra overhead.
Conclusion
The Permutations problem is a fundamental example of using recursive backtracking to explore all possible arrangements of a set of elements. By systematically selecting and deselecting elements while ensuring that each element is used exactly once in each permutation, we can efficiently generate all valid permutations of a given array.
Understanding this approach not only helps in solving similar combinatorial problems but also reinforces essential concepts in recursion, backtracking, and algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and accessible, especially for beginners. By carefully managing the state and making strategic choices at each step, complex permutation problems become manageable and solvable with clarity and confidence.