Problem of The Day: Permutations
4 min read
867 words
Problem Statement
Solution [accepted]
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(start, arr):
if start == len(arr):
res.append(arr[:])
return
for i in range(start, len(nums)):
arr[i], arr[start] = arr[start], arr[i]
backtrack(start + 1, arr) # common mistake I always make: start + 1 instead of i + 1
arr[i], arr[start] = arr[start], arr[i]
backtrack(0, nums)
return res
- time: O(n*n!)
- space: O(n*n!)
Visualization:
[1, 2, 3] start=0
|
┌────────────────────┼────────────────────┐
│ │ │
swap(0,0) swap(0,1) swap(0,2)
[1,2,3] [2,1,3] [3,2,1]
start=1 start=1 start=1
| | |
┌─────────┴─────────┐ ┌────────┴────────┐ ┌────────┴────────┐
│ │ │ │ │ │
swap(1,1) swap(1,2) swap(1,1) swap(1,2) swap(1,1) swap(1,2)
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,2,1] [3,1,2]
start=2 start=2 start=2 start=2 start=2 start=2
| | | | | |
swap(2,2) swap(2,2) swap(2,2) swap(2,2) swap(2,2) swap(2,2)
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,2,1] [3,1,2]
start=3 start=3 start=3 start=3 start=3 start=3
| | | | | |
APPEND! APPEND! APPEND! APPEND! APPEND! APPEND!
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,2,1] [3,1,2]
If we do backtrack(i + 1, arr), this will be the recursive tree which is wrong.
[1, 2, 3] start=0, i=0
|
┌────────────────────┼────────────────────┐
│ │ │
swap(0,0) swap(0,1) swap(0,2)
[1,2,3] [2,1,3] [3,2,1]
i=0, call i=1, call i=2, call
btk(i+1=1) btk(i+1=2) btk(i+1=3)
| | |
start=1, i=1 start=2, i=2 start=3 ✓
| |
┌────────┴────────┐ | APPEND!
│ │ | [3,2,1]
swap(1,1) swap(1,2) swap(2,2)
[1,2,3] [1,3,2] [2,1,3]
i=1, call i=2, call i=2, call
btk(i+1=2) btk(i+1=3) btk(i+1=3)
| | |
start=2, i=2 start=3 ✓ start=3 ✓
| | |
swap(2,2) APPEND! APPEND!
[1,2,3] [1,3,2] [2,1,3]
i=2, call
btk(i+1=3)
|
start=3 ✓
|
APPEND!
[1,2,3]
Editorial
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(curr):
if len(curr) == len(nums):
ans.append(curr[:])
return
for num in nums:
if num not in curr:
curr.append(num)
backtrack(curr)
curr.pop()
ans = []
backtrack([])
return ans
public class Solution {
public IList<IList<int>> Permute(int[] nums) {
List<IList<int>> ans = new List<IList<int>>();
Backtrack(new List<int>(), ans, nums);
return ans;
}
void Backtrack(List<int> curr, List<IList<int>> ans, int[] nums) {
if (curr.Count == nums.Length) {
ans.Add(new List<int>(curr));
return;
}
foreach (int num in nums) {
if (!curr.Contains(num)) {
curr.Add(num);
Backtrack(curr, ans, nums);
curr.RemoveAt(curr.Count - 1);
}
}
}
}
Visualization:
[] curr=[]
|
┌───────────────────┼───────────────────┐
│ │ │
append(1) append(2) append(3)
[1] [2] [3]
| | |
┌──────┴──────┐ ┌──────┴──────┐ ┌──────┴──────┐
│ │ │ │ │ │
append(2) append(3) append(1) append(3) append(1) append(2)
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
│ │ │ │ │ │
append(3) append(2) append(3) append(1) append(2) append(1)
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
| | | | | |
len=3 ✓ len=3 ✓ len=3 ✓ len=3 ✓ len=3 ✓ len=3 ✓
| | | | | |
APPEND! APPEND! APPEND! APPEND! APPEND! APPEND!
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
| | | | | |
pop(3) pop(2) pop(3) pop(1) pop(2) pop(1)
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
pop(2) pop(3) pop(1) pop(3) pop(1) pop(2)
[1] [1] [2] [2] [3] [3]
| | | | | |
pop(1) pop(1) pop(2) pop(2) pop(3) pop(3)
[] [] [] [] [] []
Leave a comment