Permutations
Our solution generates all permutations of a given array by utilizing a recursive backtracking approach. The idea is to explore every possible way of arranging the elements by swapping them at each recursive call.
Here's a breakdown of how the algorithm works:
-
We define a helper function (
backtrack) that recursively builds the permutations. This function takes two parameters:start(the index from where we start permuting) andend(the length of the array). -
The base case occurs when
start == end, meaning that a complete permutation has been formed. We add a copy of the current permutation (stored innums) to the result. -
In each recursive call, we iterate over the elements starting from the
startindex. For each element at positioni, we:- Swap the elements at
startandito bring a new element into the current position. - Recursively call
backtrackwithstart + 1, moving to the next index to fill. - After the recursive call, we swap back the elements to restore the original order and continue exploring other possibilities.
- Swap the elements at
-
This process continues until all permutations are generated.
The swapping ensures that we explore every possible combination of the elements.
from typing import List
def permute(nums: List[int]) -> List[List[int]]:
def backtrack(start: int, end: int):
if start == end:
result.append(nums[:])
for i in range(start, end):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1, end)
nums[start], nums[i] = nums[i], nums[start]
result = []
backtrack(0, len(nums))
return resultTime Complexity: The time complexity of this solution is O(n * n!), where n is the number of elements in the array. The reason for this is that generating each permutation takes O(n) time, and there are n! permutations.
Space Complexity: The space complexity is O(n!) due to the storage of all permutations in the result list. Additionally, the recursion stack uses O(n) space for the recursive calls, but this is dominated by the result storage.
function permute(nums) { if (nums.length <= 1) { return [nums]; } const prevPermutations = permute(nums.slice(0, nums.length-1)); const currentNum = nums[nums.length-1]; const permutations = new Set(); for (let prev of prevPermutations) { for (let i=0; i < prev.length; i++) { permutations.add([...prev.slice(0, i), currentNum, ...prev.slice(i)]); } permutations.add([...prev, currentNum]); } return [...permutations]; }