46. Permutations

Difficulty: Medium
Category: Backtracking, Recursion

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Examples

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Approach

This is a classic backtracking problem that requires generating all possible permutations of a given array. There are two main approaches:

  1. Backtracking with Swapping: Generate permutations by swapping elements in-place
  2. STL next_permutation: Use Python STL’s built-in permutation generator

Algorithm 1: Backtracking with Swapping

  1. Start from index 0 and try each element at current position
  2. Swap elements to place them at current position
  3. Recursively generate permutations for remaining positions
  4. Backtrack by swapping back to original positions
  5. Base case: When we’ve placed all elements, add current permutation

Algorithm 2: STL next_permutation

  1. Sort the array to get lexicographically smallest permutation
  2. Use do-while loop with next_permutation() to generate all permutations
  3. Add each permutation to result vector
  4. Continue until no more permutations exist

Solution

Solution 1: Backtracking with Swapping

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        self.permuteHelper(nums, 0, result)
        return result
    
    def permuteHelper(self, nums: list[int], idx: int, result: list[list[int]]) -> None:
        if idx == len(nums):
            result.append(nums[:])  # Create a copy
            return
        for i in range(idx, len(nums)):
            nums[idx], nums[i] = nums[i], nums[idx]  # Swap
            self.permuteHelper(nums, idx + 1, result)
            nums[idx], nums[i] = nums[i], nums[idx]  # Backtrack

Solution 2: STL next_permutation

from itertools import permutations

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        return list(permutations(nums))

Explanation

Solution 1: Backtracking with Swapping

Step-by-Step Process:

  1. Base Case: When idx == nums.size(), we’ve generated a complete permutation
  2. Recursive Case: For each position idx, try every element from idx to n-1
  3. Swap: Place element at position i to position idx
  4. Recurse: Generate permutations for remaining positions (idx + 1)
  5. Backtrack: Swap back to restore original state

Example Walkthrough for nums = [1,2,3]:

Initial: [1,2,3], idx=0
├─ Swap(0,0): [1,2,3] → Recurse with idx=1
│  ├─ Swap(1,1): [1,2,3] → Recurse with idx=2
│  │  └─ Swap(2,2): [1,2,3] → idx=3, add [1,2,3]
│  └─ Swap(1,2): [1,3,2] → Recurse with idx=2
│     └─ Swap(2,2): [1,3,2] → idx=3, add [1,3,2]
├─ Swap(0,1): [2,1,3] → Recurse with idx=1
│  ├─ Swap(1,1): [2,1,3] → Recurse with idx=2
│  │  └─ Swap(2,2): [2,1,3] → idx=3, add [2,1,3]
│  └─ Swap(1,2): [2,3,1] → Recurse with idx=2
│     └─ Swap(2,2): [2,3,1] → idx=3, add [2,3,1]
└─ Swap(0,2): [3,2,1] → Recurse with idx=1
   ├─ Swap(1,1): [3,2,1] → Recurse with idx=2
   │  └─ Swap(2,2): [3,2,1] → idx=3, add [3,2,1]
   └─ Swap(1,2): [3,1,2] → Recurse with idx=2
      └─ Swap(2,2): [3,1,2] → idx=3, add [3,1,2]

Solution 2: STL next_permutation

Step-by-Step Process:

  1. Sort array to get lexicographically smallest permutation
  2. Generate permutations using next_permutation() in do-while loop
  3. Add each permutation to result vector
  4. Continue until next_permutation() returns false

Example Walkthrough for nums = [1,2,3]:

Sorted: [1,2,3]
1. [1,2,3] → Add to result
2. [1,3,2] → Add to result  
3. [2,1,3] → Add to result
4. [2,3,1] → Add to result
5. [3,1,2] → Add to result
6. [3,2,1] → Add to result
7. next_permutation returns false → Stop

Complexity Analysis

Solution 1: Backtracking with Swapping

Time Complexity: O(n! × n)

  • Permutations: n! permutations generated
  • Each permutation: O(n) time to copy array
  • Total: O(n! × n)

Space Complexity: O(n)

  • Recursion depth: O(n) for the call stack
  • No additional space for storing permutations during generation

Solution 2: STL next_permutation

Time Complexity: O(n! × n)

  • Permutations: n! permutations generated
  • Each permutation: O(n) time for next_permutation() and copying
  • Total: O(n! × n)

Space Complexity: O(1)

  • No recursion: Iterative approach
  • No additional space beyond input and output

Key Insights

  1. Backtracking Pattern: Classic recursive approach with state restoration
  2. In-place Generation: Swapping allows generating permutations without extra space
  3. STL Efficiency: next_permutation() is highly optimized
  4. Lexicographic Order: STL approach generates permutations in sorted order
  5. State Management: Proper backtracking ensures all possibilities are explored

Comparison of Approaches

Approach Time Space Advantages Disadvantages
Backtracking O(n! × n) O(n) Educational, flexible Recursive overhead
STL O(n! × n) O(1) Concise, optimized Less control over order

Alternative Approaches

Approach 3: Backtracking with Visited Array

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        current = []
        used = [False] * len(nums)
        self.backtrack(nums, current, used, result)
        return result
    
    def backtrack(self, nums: list[int], current: list[int], 
                  used: list[bool], result: list[list[int]]) -> None:
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            
            used[i] = True
            current.append(nums[i])
            self.backtrack(nums, current, used, result)
            current.pop()
            used[i] = False

Approach 4: Iterative with Stack

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        stack = [[]]
        
        while stack:
            current = stack.pop()
            
            if len(current) == len(nums):
                result.append(current)
                continue
            
            for num in nums:
                if num not in current:
                    next_perm = current + [num]
                    stack.append(next_perm)
        
        return result

When to Use Each Approach

Use Backtracking with Swapping when:

  • Memory is limited (O(n) space vs O(n!) for visited approach)
  • Need to understand the algorithm deeply
  • Custom modifications are required

Use STL next_permutation when:

  • Code simplicity is priority
  • Lexicographic order is desired
  • Performance is critical (highly optimized)

Use Visited Array when:

  • Clarity is more important than space
  • Need to track which elements are used
  • Modifying the original array is not allowed

Key Concepts

  1. Permutations: All possible arrangements of elements
  2. Backtracking: Systematic exploration with state restoration
  3. Recursion: Divide problem into smaller subproblems
  4. State Space: All possible configurations to explore
  5. Pruning: Avoiding invalid or duplicate states

This problem is fundamental for understanding backtracking algorithms and is commonly used in interviews to test recursive thinking and state management skills.