Skip to content

46. Permutations

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Brute Force Generate all possible arrangements by trying every element at each position. For each position, iterate through all remaining elements and recursively build permutations. \(O(n! \cdot n)\) \(O(n! \cdot n)\)
Recursive (Backtracking) Recursively generate permutations by taking the first element and inserting it at all positions in permutations of remaining elements. Base case returns when only one element remains. \(O(n!)\) \(O(n!)\)
Iterative (Deque) Use a deque to iteratively build permutations. For each number, insert it at all possible positions in existing permutations. Start with empty permutation and expand by adding each number at every valid position. \(O(n!)\) \(O(n!)\)

Implementation

Iterative
from collections import deque
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = deque([[]])
        for num in nums:
            for _ in range(len(result)):
                perm = result.popleft()
                for i in range(len(perm)+1):
                    result.append(
                        perm[:i] + [num] + perm[i:]
                    )
        return list(result)
Recursive
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums]

        result = []
        perms = self.permute(nums[1:])
        for perm in perms:
            for i in range(len(perm)+1):
                result.append(
                    perm[:i] + [nums[0]] + perm[i:]
                )
        return result