Permutations
- 3 min read
- Ae-medium
- LC-Medium
- Algoexpert
3 years ago
https://www.algoexpert.io/questions/permutations
Solution
- In short, try all numbers in the first position. For each number in the first position, try all other numbers in the second position. For each pair of numbers in the first and second positions, try all other numbers in the third position, and so on.
| Time | Space | Explanation |
|---|---|---|
O(n * n!) | O(n) | See below |
- Time: There are n! permutations. For each permutation, we need O(n) to copy
currintoans - Space: Maximum depth of call stack at any time is O(n)
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
self.backtrack([], nums, ans)
return ans
def backtrack(self, curr, nums, ans):
if len(curr) == len(nums):
ans.append(curr[:])
return
for num in nums:
if num not in curr:
curr.append(num)
self.backtrack(curr, nums, ans)
curr.pop()
Super Small Solution
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
def backtrack(curr):
if len(curr) == len(nums):
ans.append(curr)
return
for num in nums:
if num not in curr:
backtrack(curr + [num])
backtrack([])
return ans
Alternate Logic (BETTER?)
- Start out empty, and incrementally add one number to each position in our permutations
- i.e. start empty: []
- take first number 1 and add: [1]
- then next number is 2.
- Go through all our permutations,
- go each permutation, go through each position
- and at each position, insert our next number
- So in our case, [1] would become [1, 2], [2, 1]
- then if we do with three,
- [1, 2] turns to [3, 1, 2], [1, 3, 2], [1, 2, 3]
- [2, 1] turns to [3, 2, 1], [2, 3, 1], [2, 1, 3]
- This gives us all our permutations
function permute(nums: number[]): number[][] {
let perms = [[]]; // Start with a list containing an empty permutation
for (let num of nums) { // Iterate through each number in the input array
const newPerms = []; // Initialize a new list for permutations with the current number added
for (let perm of perms) { // Iterate through existing permutations
for (let i = 0; i <= perm.length; i++) { // Iterate through all possible insertion positions
const permCopy = [...perm]; // Create a copy of the current permutation
permCopy.splice(i, 0, num); // Insert the current number at position i
newPerms.push(permCopy); // Add the new permutation to newPerms
}
}
perms = newPerms; // Update the list of permutations for the next iteration
}
return perms;
};