💬 Discord
Sign In
NeetCode #492LC-46MediumBacktrackingNC 150NC 250
← Back to All Problems

#492 · #46 · Permutations(全排列)

📌 Problem Statement & Constraints

Given an array nums of distinct integers, return all possible permutations in any order. Constraints: 1 <= nums.length <= 6, -10 <= nums[i] <= 10.

💡 Core Algorithmic Approaches

  1. Build the permutation position by position, tracking which elements have been used.
  2. At each step, try every unused element, recurse, then unmark it.
  3. A permutation is complete when the path length equals the array length.
  4. An alternative avoids the used array by swapping elements in place, which uses less memory but reorders the input.

💻 Benchmark Python3 Implementation

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)

        def dfs(path: List[int]) -> None:
            if len(path) == len(nums):
                res.append(path[:])        # complete permutation
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs(path)
                path.pop()                 # backtrack
                used[i] = False

        dfs([])
        return res


# Swap-based variant: no `used` array, but the input is reordered
class Solution2:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(i: int) -> None:
            if i == len(nums):
                res.append(nums[:])
                return
            for j in range(i, len(nums)):
                nums[i], nums[j] = nums[j], nums[i]
                dfs(i + 1)
                nums[i], nums[j] = nums[j], nums[i]

        dfs(0)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * n!): there are n! permutations, each taking O(n) to copy.
💾 Space Complexity
O(n) for the recursion path and the used array.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to reset used[i] = False: later branches would see a corrupted state.
  • Appending path without copying: all entries would alias the same list.
  • Generating combinations instead of permutations: order matters here, so every position tries every unused element.
  • Assuming elements are unique: they are guaranteed to be, so no deduplication is needed (contrast with 47).