LeetCode 46: Permutations Solution in Python Explained
Problem Statement
LeetCode 46, Permutations, is a medium-level problem where you’re given an array of distinct integers nums. Your task is to return all possible permutations of the array. A permutation is a rearrangement of the numbers, and since the numbers are distinct, all permutations are unique. Return the result as a list of lists in any order.
Constraints
- 1 <= nums.length <= 6: Array length is between 1 and 6.
- -10 <= nums[i] <= 10: Each element is between -10 and 10.
- All integers in nums are distinct.
Example
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 6 permutations of [1,2,3].
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Explanation: Two permutations of [0,1].
Input: nums = [1]
Output: [[1]]
Explanation: Single element has one permutation.
Understanding the Problem
How do you solve LeetCode 46: Permutations in Python? For nums = [1,2,3], generate all 6 possible orderings: [1,2,3], [1,3,2], etc. With distinct numbers, we need every arrangement without repetition. We’ll explore two approaches: a Backtracking Solution (optimal and primary) and an Alternative with Heap’s Algorithm (iterative and clever). The backtracking method builds permutations by swapping or selecting numbers recursively.
Solution 1: Backtracking Approach (Primary)
Explanation
Use backtracking to build permutations by selecting each number into a current permutation, marking it used, and recursing until all numbers are included. Backtrack by removing the number and trying the next.
Here’s a flow for [1,2,3]:
Start: []
Add 1: [1] -> [1,2] -> [1,2,3] (add)
Backtrack: [1] -> [1,3] -> [1,3,2] (add)
Backtrack: [] -> [2] -> [2,1] -> [2,1,3] (add)
- Initialize Result.
- List to store permutations.
- Backtrack.
- Build permutation, track used numbers.
- Base Case.
- When permutation length equals nums length, add it.
- Return Result.
Step-by-Step Example
Example 1: nums = [1,2,3]
We need all 6 permutations.
- Goal: Generate all permutations.
- Result for Reference: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
- Start: nums = [1,2,3], result = [], curr = [], used = set().
- Step 1: Add 1.
- curr = [1], used = {1}.
- Add 2, curr = [1,2], used = {1,2}.
- Add 3, curr = [1,2,3], len = 3, add to result, backtrack.
- Step 2: Backtrack, curr = [1], used = {1}.
- Add 3, curr = [1,3], used = {1,3}.
- Add 2, curr = [1,3,2], add to result, backtrack.
- Step 3: Backtrack, curr = [], used = {}.
- Add 2, curr = [2], used = {2}.
- Add 1, curr = [2,1], used = {1,2}.
- Add 3, curr = [2,1,3], add to result.
- Step 4: Continue, generate all 6 permutations.
- Finish: Return [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
Example 2: nums = [0,1]
We need [[0,1],[1,0]].
- Start: curr = [], used = {}.
- Step 1: Add 0, curr = [0].
- Add 1, curr = [0,1], add to result.
- Step 2: Backtrack, curr = [].
- Add 1, curr = [1].
- Add 0, curr = [1,0], add to result.
- Finish: Return [[0,1],[1,0]].
How the Code Works (Backtracking)
Here’s the Python code with line-by-line explanation:
def permute(nums: list[int]) -> list[list[int]]:
# Line 1: Initialize result
result = []
# Line 2: Backtracking helper
def backtrack(curr: list[int], used: set[int]) -> None:
# Line 3: Base case: full permutation
if len(curr) == len(nums):
result.append(curr[:])
return
# Line 4: Try each number
for num in nums:
# Line 5: Skip if used
if num not in used:
# Line 6: Add to current permutation
curr.append(num)
used.add(num)
# Line 7: Recurse
backtrack(curr, used)
# Line 8: Backtrack
curr.pop()
used.remove(num)
# Line 9: Start backtracking
backtrack([], set())
# Line 10: Return all permutations
return result
Alternative: Heap’s Algorithm Approach
Explanation
Use Heap’s Algorithm to generate permutations iteratively by swapping elements in-place. It reduces the problem size by fixing elements and permuting the rest, using a clever swap pattern.
- Base Case.
- Single element, add to result.
- Iterate and Swap.
- Generate permutations by swapping.
- Return Result.
Step-by-Step Example (Alternative)
For nums = [1,2,3]:
- Start: result = [], nums = [1,2,3].
- Step 1: k = 3, add [1,2,3].
- Step 2: Swap 1<->2, [2,1,3], add, swap 1<->3, [3,1,2], add.
- Step 3: Swap back, recurse on [2,3], [3,2], etc.
- Finish: Generate all 6 permutations.
How the Code Works (Heap’s)
def permuteHeap(nums: list[int]) -> list[list[int]]:
# Line 1: Initialize result
result = []
# Line 2: Heap’s algorithm helper
def generate(k: int, arr: list[int]) -> None:
if k == 1:
result.append(arr[:])
return
# Line 3: Generate permutations
for i in range(k):
generate(k - 1, arr)
# Line 4: Swap based on parity
if k % 2 == 0:
arr[i], arr[k-1] = arr[k-1], arr[i]
else:
arr[0], arr[k-1] = arr[k-1], arr[0]
# Line 5: Start generation
generate(len(nums), nums)
# Line 6: Return result
return result
Complexity
- Backtracking:
- Time: O(n!) – Generate all n! permutations.
- Space: O(n) – Recursion stack and current permutation.
- Heap’s Algorithm:
- Time: O(n!) – Generate all permutations iteratively.
- Space: O(n!) – Store all permutations (O(1) extra if yielding).
Efficiency Notes
Both are O(n!) time due to generating all permutations. Backtracking is more intuitive and flexible; Heap’s is iterative and space-efficient if modified to yield results.
Key Insights
Tips to master LeetCode 46:
- Build Incrementally: Add one number at a time.
- Track Usage: Use a set or swaps to avoid repeats.
- All Possible: Ensure every order is covered.
Additional Example
For nums = [1,2]:
- Goal: [[1,2],[2,1]].
- Backtracking: [1,2], [2,1].
- Result: [[1,2],[2,1]].
Edge Cases
- Single Element: [1] – Return [[1]].
- Two Elements: [0,1] – Return [[0,1],[1,0]].
- Max Length: [1,2,3,4,5,6] – Return 720 permutations.
Final Thoughts
The Backtracking solution is a classic for LeetCode 46 in Python—clear, versatile, and perfect for permutations. For a related challenge, try LeetCode 45: Jump Game II to switch to greedy thinking! Ready to permute? Solve LeetCode 46 on LeetCode now and test it with [1,2,3] or [0,1,2] to see all the possibilities unfold. Dive in and rearrange away!