Pseudo-code for a fixed length of 3:

text
results = []
for i in nums:
  for j in nums:
    if j != i:
      for k in nums:
        if k != i and k != j:
          results.add([i, j, k])

Why this fails:

1. Variable Constraints: The input length $N$ is variable (1 to 6). We cannot write code with a dynamic number of nested loops.
2. Scalability: Even if we could write dynamic loops, checking for uniqueness (e.g., if k != i and k != j) becomes computationally expensive ($O(N)$ inside the innermost loop) as $N$ grows.
3. Complexity: While the time complexity of generating permutations is inherently high, the implementation complexity of an iterative brute force approach for variable $N$ is impractical.

Core Insight for Permutations

The core insight for solving LeetCode 46 is to view the permutation process as a series of decisions: "Which number goes into index 0? Which remaining number goes into index 1?" and so on.

Instead of creating new arrays for every recursive call or maintaining a separate boolean "visited" array (which increases space complexity), we can maintain the state in-place within the input array.

The Invariant: At any recursive step acting on index first, the subarray nums[0...first-1] is fixed and represents the current partial permutation. The subarray nums[first...n-1] contains all the candidates available to be placed at index first.

By swapping elements from the available pool (indices first to n-1) into the current position (first), we explore all possibilities for that specific slot. After the recursive call returns, we backtrack by swapping the element back to its original position. This restores the array to the state it was in before the decision, allowing the algorithm to explore the next candidate cleanly.

Visual Description: Imagine a recursion tree. At the root (index 0), we have branches for every number in the array. If we pick 1 to be at index 0, we move down a branch where 1 is fixed. The next level (index 1) branches out for every remaining number (e.g., 2 and 3). This continues until we reach a leaf node where all positions are filled. The "backtracking" is the movement back up the tree branch to the previous node to take a different path.

Execution Flow

Consider nums = [1, 2, 3].

1. Start backtrack(0):
   • i = 0: Swap nums[0] with nums[0]. Array is [1, 2, 3].
   • Recurse backtrack(1):
     • i = 1: Swap nums[1] with nums[1]. Array is [1, 2, 3].
     • Recurse backtrack(2):
       • i = 2: Swap nums[2] with nums[2]. Array is [1, 2, 3].
       • Recurse backtrack(3): Base case met. Add [1, 2, 3]. Return.
       • Backtrack: Swap nums[2] with nums[2].
     • Backtrack: Swap nums[1] with nums[1].
     • i = 2: Swap nums[1] with nums[2]. Array is [1, 3, 2].
     • Recurse backtrack(2):
       • (Recursion continues, eventually adding [1, 3, 2]).
   • Backtrack: Swap nums[0] with nums[0].
   • i = 1: Swap nums[0] with nums[1]. Array is [2, 1, 3].
   • (Process continues for all branches starting with 2, then 3).

Proof of Correctness

The algorithm is correct because it exhaustively explores the state space defined by $P(N, N)$.

1. Completeness: The loop for i from first to n-1 ensures that every available number gets a chance to sit at the index first.
2. Non-duplication: Since the input array contains distinct integers and we systematically swap every element into every position exactly once per recursive level, we never generate the same permutation twice.
3. State Restoration: The backtracking step (the second swap) ensures that when we return to the parent node in the recursion tree, the array is identical to how it was before the child call. This invariant ensures that side effects from one branch do not bleed into the next branch.

Reference Implementation

C++ Solution for LeetCode 46

cpp
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
        // Base case: if start index reaches the end, we have a complete permutation
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }

        // Iterate over all possible candidates for the current position 'start'
        for (int i = start; i < nums.size(); i++) {
            // Swap the current element with the candidate element
            swap(nums[start], nums[i]);
            
            // Recurse for the next position
            backtrack(nums, start + 1, result);
            
            // Backtrack: undo the swap to restore the original state
            swap(nums[start], nums[i]);
        }
    }
};

Java Solution for LeetCode 46

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        // Convert int[] to List<Integer> to facilitate swapping and storage
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) {
            numsList.add(num);
        }
        
        backtrack(numsList, 0, result);
        return result;
    }
    
    private void backtrack(List<Integer> nums, int start, List<List<Integer>> result) {
        // Base case: if start index reaches the size, permutation is complete
        if (start == nums.size()) {
            result.add(new ArrayList<>(nums)); // Important: add a COPY
            return;
        }
        
        for (int i = start; i < nums.size(); i++) {
            // Swap current index with the loop index
            Collections.swap(nums, start, i);
            
            // Recurse down the decision tree
            backtrack(nums, start + 1, result);
            
            // Backtrack: swap back to restore state
            Collections.swap(nums, start, i);
        }
    }
}

Python Solution for LeetCode 46

python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtrack(start_index):
            # Base case: if start_index is at the end, we found a permutation
            if start_index == len(nums):
                result.append(nums[:]) # Important: append a COPY (slice)
                return
            
            for i in range(start_index, len(nums)):
                # Swap the current element with the candidate
                nums[start_index], nums[i] = nums[i], nums[start_index]
                
                # Recurse for the next index
                backtrack(start_index + 1)
                
                # Backtrack: undo the swap
                nums[start_index], nums[i] = nums[i], nums[start_index]
        
        backtrack(0)
        return result

Q: Why does my solution contain duplicates or miss permutations?

• Mistake: Forgetting the backtracking step (the second swap).
• Why: If you don't swap back, the array remains modified for the next iteration of the loop. The assumption that nums[start...end] contains the set of available candidates breaks.
• Consequence: The algorithm explores an invalid state space, resulting in incorrect permutations and often missing valid ones.

Q: Can I use if path contains current_num instead of swapping?

• Mistake: Using a linear scan (O(N)) to check if a number is already used in the current partial permutation.
• Why: While this logic is correct for generating permutations, checking membership in a list inside the recursion adds an extra $O(N)$ factor.
• Consequence: The time complexity degrades to $O(N^2 \cdot N!)$. While acceptable for $N=6$, it shows a lack of understanding of optimal state management (swapping or using a boolean visited array).