L12. Print all Permutations of a String / Array | Recursion | Approach 1

This comprehensive study note explores the foundational algorithmic problem of generating all permutations of a given string or array using recursion. We analyze the explicit state-space tree, frequency map tracking, backtracking mechanics, and exact complexity bounds.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given an array or string of distinct integers/characters of size $n$, the objective is to return all possible permutations.

• Mathematical Expectation: For an input of size $n$, the total number of permutations is given by the factorial function:

For example, given an array of size $3$ ([1, 2, 3]), $3! = 3 \times 2 \times 1 = 6$ total permutations will be generated ([1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]).

• Interview Significance: Generating permutations is a classic interview question frequently asked in technical assessments for companies like Google, Amazon, and Microsoft. Mastering this recursion pattern forms the bedrock for solving complex combinatorial search problems.

2. Core Mental Model: The Frequency Map Strategy (Approach 1)

To systematically generate permutations without missing combinations or generating duplicates, we visualize the process using a Decision Tree supported by a Frequency Map / Boolean Tracking Array.

Real-Life Analogy: Picking Items from a Box

Analogy: Imagine standing in front of a box containing $n$ distinct numbered balls. You want to line them up one by one in a row of length $n$.

1. For the first spot, you can reach in and pick any available ball (say, ball 1, 2, or 3). Once picked, that ball is removed from the choice pool.
2. For the second spot, you can only choose from the remaining balls.
3. You repeat this until all spots are filled. If you want to try a different arrangement, you put the last picked ball back into the box (backtracking) and pick a different ball.

3. Step-by-Step State-Space Tree Walkthrough

Let us trace the recursion tree for the input array [1, 2, 3] ($n = 3$).

4. The Backtracking Mechanics (State Reset)

When recursion returns from a deeper call stack, we must undo our choices so that sibling branches can evaluate correctly. This process is known as Backtracking.

Choose Step:
   1. Mark element as visited in frequency map: freq[i] = 1
   2. Add element to temporary data structure (DS): DS.add(arr[i])
   3. Recurse: solve()

Un-choose (Backtracking) Step:
   1. Remove element from temporary data structure: DS.removeLast()
   2. Unmark element in frequency map: freq[i] = 0

5. Complete Flow Walkthrough

The following step-by-step trace demonstrates how the recursive function navigates through the array indices:

6. Java Implementation

Below is the clean, production-ready Java implementation corresponding to Approach 1 using a frequency map/array.

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

public class Permutations {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> ds = new ArrayList<>();
        int[] freq = new int[nums.length]; // Frequency map initialized to 0
        
        recursePermutations(nums, ds, ans, freq);
        return ans;
    }

    private static void recursePermutations(int[] nums, List<Integer> ds, List<List<Integer>> ans, int[] freq) {
        // Base Case: If temporary list size matches array size, we found a valid permutation
        if (ds.size() == nums.length) {
            ans.add(new ArrayList<>(ds)); // Store a deep copy of the permutation
            return;
        }

        // Try picking elements from index 0 to n - 1
        for (int i = 0; i < nums.length; i++) {
            // Check if the element has already been picked in the current path
            if (freq[i] == 0) {
                freq[i] = 1;              // Mark as picked
                ds.add(nums[i]);          // Add to current permutation path
                
                recursePermutations(nums, ds, ans, freq); // Recursive call
                
                // Backtrack: Undo choices for sibling branches
                ds.remove(ds.size() - 1); 
                freq[i] = 0;              
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = permute(nums);
        System.out.println("All Permutations: " + result);
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Permutations Definition: An arrangement of items where order matters, totaling $n!$ unique configurations for $n$ distinct elements.
• Approach 1 Mechanics: Utilizes a frequency tracking array (freq[]) combined with a temporary list (ds) to keep track of included elements during state transitions.
• State Selection Rule: An element can only be selected if its frequency flag is 0 (unvisited in the current recursion branch).
• Mandatory Backtracking: After a recursive call returns, always pop the last inserted element and reset its frequency flag to 0 to allow correct evaluation of alternative paths.
• Base Case Trigger: Fires when ds.size() == arr.length, at which point a deep copy of the current permutation sequence is committed to the result container.
• Time Bound: Dominated by the factorial growth rate $\mathcal{O}(n! \times n)$, making it optimal for small to medium input sizes.