L13. Print all Permutations of a String/Array | Recursion | Approach - 2

In this chapter, we explore an optimized, in-place algorithmic approach to generate all possible permutations of a given string or array. Building upon the previous recursive solution that required external frequency maps and extra data structures, this approach utilizes element swapping and backtracking to achieve space efficiency while systematically exploring permutation branches.

1. Why Do We Need This? (Problem Statement & Limitations of Approach 1)

In the standard frequency-map-based approach (Approach 1), generating permutations requires maintaining auxiliary data structures:

• A frequency boolean/map array to track which elements have already been included in the current recursive path.
• Temporary lists to build individual permutations before storing them in the final answer collection.

The Space Bottleneck: While Approach 1 is intuitive, maintaining extra data structures incurs unnecessary space overhead. For a problem of size $n$, keeping track of elements via auxiliary maps adds $\mathcal{O}(n)$ extra memory at every level of the recursive stack, independent of the recursion depth itself.

The Optimized Goal: Can we generate all permutations without any extra frequency maps or tracking arrays, modifying the input array directly and restoring its state afterward? Yes—by using an in-place swapping technique.

2. Core Mental Model: The Swapping Strategy

The core intuition behind Approach 2 is that every element in the array must be given a chance to occupy the current index position.

Real-Life Analogy: Assigning Leadership Positions

Imagine you have $n$ candidates standing in a line, and you need to fill $n$ leadership positions sequentially from left to right (index $0$ to $n-1$).

• For the 1st position (index $0$), you invite every candidate one by one to step up to the front by swapping their position with the current candidate at index $0$.
• Once a candidate is fixed at the front, you lock that position and move to the 2nd position (index $1$), repeating the process for the remaining candidates.
• After exploring all possibilities with a candidate in the front, you swap them back (backtracking) to restore the line to its original order before trying the next candidate.

3. Naive vs. Better Approach

4. Step-by-Step Recursive Tree Evolution

Let us trace the execution for an array of size 3: [1, 2, 3].

5. Complete Flow Walkthrough

1. Initialization: The main function calls the recursive worker function passing index = 0, the input array/vector, and the answer container.
2. Loop Execution: At the current index, a loop runs from i = index up to n - 1.
3. The Swap Action: We swap the element at index with the element at i: swap(arr[index], arr[i]). This places a candidate at the current fixed position.
4. Recursive Dive: We recursively call the function for the next position: recurse(index + 1, arr, ans).
5. Backtracking (Re-Swap): Upon returning from the recursive call, we must restore the array to its original state before the next iteration of the loop. We do this by swapping back: swap(arr[index], arr[i]).
6. Base Case: When index == n, it means all positions have been successfully determined. We convert the array into a list/vector and add it to the final answer collection, then return.

6. Implementation Code

Java Implementation

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

public class Permutations {
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        recurse(0, nums, ans);
        return ans;
    }

    private void recurse(int index, int[] nums, List<List<Integer>> ans) {
        // Base Case: If pointer reaches the end of the array
        if (index == nums.length) {
            List<Integer> ds = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                ds.add(nums[i]);
            }
            ans.add(new ArrayList<>(ds));
            return;
        }

        // Try every element from 'index' to 'nums.length - 1' at the current position
        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);          // Do
            recurse(index + 1, nums, ans); // Recurse
            swap(nums, index, i);          // Backtrack (Undo Swap)
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

C++ Implementation

#include <vector>

class Solution {
private:
    void recurse(int index, std::vector<int>& nums, std::vector<std::vector<int>>& ans) {
        // Base Case: If pointer reaches the end of the array
        if (index == nums.size()) {
            ans.push_back(nums);
            return;
        }

        // Try every element from 'index' to 'nums.size() - 1' at the current position
        for (int i = index; i < nums.size(); i++) {
            std::swap(nums[index], nums[i]); // Do
            recurse(index + 1, nums, ans);   // Recurse
            std::swap(nums[index], nums[i]); // Backtrack (Undo Swap)
        }
    }

public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> ans;
        recurse(0, nums, ans);
        return ans;
    }
};

7. Complexity Analysis

Time Complexity

• Permutations Count: There are $n!$ (n-factorial) unique permutations for an array of size $n$.
• Work per Permutation: At the base case, copying or inserting the array of size $n$ into the answer data structure takes $\mathcal{O}(n)$ time.
• Total Time Complexity: $\mathcal{O}(n! \times n)$.

Space Complexity

• Auxiliary Space: $\mathcal{O}(1)$ extra space for maps or tracking arrays, since we operate directly on the input array.
• Recursion Stack Space: The maximum depth of the recursion tree is $n$, taking $\mathcal{O}(n)$ stack space.
• Output Space: $\mathcal{O}(n! \times n)$ to store all permutations in the answer collection.
• Total Auxiliary Space Complexity: $\mathcal{O}(n)$ (excluding the output storage). This represents a significant space optimization over Approach 1.

8. Summary and Key Takeaways

• In-Place Transformation: Approach 2 eliminates the need for auxiliary frequency maps or boolean tracking arrays by leveraging element swapping.
• Positional Candidate Selection: At each recursive step index, a loop tries every candidate from index to n-1 by swapping them into the current slot.
• The Power of Backtracking: Re-swapping (swap after recursion returns) is crucial to restore the array state before testing the next candidate branch.
• Base Case Trigger: When index == n, a valid permutation is fully formed and captured.
• Space Efficiency: Reduces extra memory overhead from $\mathcal{O}(n)$ auxiliary maps down to $\mathcal{O}(1)$ extra working space (with $\mathcal{O}(n)$ recursion depth).
• Time Complexity Profile: Maintains the optimal time complexity of $\mathcal{O}(n! \times n)$ required to generate and collect all permutations.