Domain 2MediumCORE

Permutations

We are given a list of distinct integers and need to generate every possible ordering where each number appears exactly once per permutation. The output is a collection of these orderings.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Backtracking

46. Permutations

Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 1
Acceptance rate: 67.1%


Problem Breakdown

We are given a list of distinct integers and need to generate every possible ordering where each number appears exactly once per permutation. The output is a collection of these orderings.

Inputs: An array nums containing unique integers. Outputs: A 2D list (list of lists) representing all permutations. Constraints & Edge Cases:

  • Length: 1≤N≤61 \le N \le 6. This small constraint is crucial; it implies an exponential solution (O(N!)O(N!)) will pass within time limits, as the maximum output size for N=6N=6 is roughly 720 permutations.
  • Values: Integers can be negative or positive. Since we are dealing with values and not indices directly in a way that affects logic (other than uniqueness), sign doesn’t impact complexity but confirms standard integer comparison works fine.
  • Uniqueness: The problem guarantees distinct integers, so we do not need to handle duplicate permutations caused by identical input elements.

Intuition

A brute-force approach would be to generate every possible combination of length NN and check if it matches the multiset of nums. This is inefficient (O(N2⋅N!)O(N^2 \cdot N!) or worse).

The key insight here is that we are building a tree structure where each level represents filling one position in the permutation. At any point, we can pick an unused number from our input array to place at the current index and recurse for the next index. Once we reach depth NN, we have formed a valid permutation.

This naturally maps to Backtracking (Depth-First Search). We explore every branch of possibilities by picking available numbers, then “undo” that choice (backtrack) when returning from recursion so we can try other numbers for the current position.

Approach

We will use a recursive backtracking function dfs(current_path) or similar state management:

  1. State: We need to track which elements of nums have been used in the current path being built, and what that partial permutation looks like (path).
  2. Base Case: If the length of our current path equals the input array size NN, we append a copy of this path to our results list. We stop recursion here because no more elements can be added.
  3. Recursive Step: Iterate through every number in nums.
    • Check if it is already used (to avoid duplicates within one permutation).
    • If not used: Add the number to path, mark as used, and call recursion for the next depth.
    • Backtrack: Remove the number from path and unmark it so we can use it in a different branch of the tree later.

To optimize space slightly during iteration without modifying input order permanently (unless allowed), I will maintain a boolean array or set to track usage status for O(N)O(N) lookup time per step, though with distinct integers and small N, simple list removal is also acceptable but less clean functionally. I’ll use the used flag approach for clarity in explanation.

Complexity Analysis

  • Time Complexity: O(N⋅N!)O(N \cdot N!). There are N!N! permutations to generate. For each permutation of length NN, we perform work proportional to its size (copying into result list). Thus, total operations scale with the output size itself. Given constraints (N≤6N \le 6), this is well within limits.
  • Space Complexity: O(N)O(N). This accounts for the recursion stack depth and the used tracking structure or temporary path storage during traversal (excluding the space required to store the final result).

Solution

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        # Helper function for backtracking
        def backtrack(path):
            # Base case: if path length matches input size, we found a permutation
            if len(path) == len(nums):
                res.append(list(path))  # Append a copy to avoid reference issues
                return
            
            # Iterate over available numbers in nums
            for i in range(len(nums)):
                # Skip if this number is already used in the current path
                if not self.used[i]: 
                    # Choose: add element and mark as used
                    path.append(nums[i])
                    self.used[i] = True
                    
                    # Explore: recurse to fill next position
                    backtrack(path)
                    
                    # Un-choose (Backtrack): remove element and unmark for other branches
                    path.pop()
                    self.used[i] = False

        n = len(nums)
        used = [False] * n
        
        backtrack([])
        
        return res

Edge Cases Handled

  • Single Element ([1]): The loop runs once, base case triggers immediately after one iteration. Returns [[1]]. Correctly handled by the length check in recursion.
  • Negative Numbers: Logic relies on index tracking and equality checks, not value magnitude or sign comparisons for validity. Handled correctly as distinct integers are treated purely as identifiers.
  • Small Constraints (N≤6N \le 6): The solution does not optimize beyond O(N!)O(N!) because the output size itself dominates complexity; further optimization is unnecessary given input limits.