Understanding Permutations in Java

Introduction & Problem Explanation

The Permutations problem asks us to generate all possible permutations (different arrangements or orderings) of an array of distinct integers, nums.

A permutation is an arrangement of all members of a set into some sequence or linear order. For a set of size n, the total number of unique permutations is exactly n! (n factorial). For instance, if nums = [1, 2, 3], the output contains 3! = 6 combinations:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Generating all permutations requires us to explore all branches of a state space tree of size O(n!). Backtracking combined with a fast lookup buffer (like a boolean array or a set) is the standard method for this task.

The Algorithmic Approach

Backtracking Search with Used Buffer (O(n * n!) Time, O(n) Space)

We build our permutations recursively, building a single permutation list path of length n step-by-step.

• Base Case: If the size of path equals nums.length, we have formed a complete permutation. We make a copy of path and add it to our results list.
• Recursive Exploration: We loop through all numbers in nums. For each number num:
  • If the number is already used in our current path, we skip it to prevent reusing elements. To do this efficiently, we can use a boolean array used where used[i] tracks whether nums[i] is currently in our path. This lookup is O(1), which is much faster than calling path.contains(num), which takes O(n).
  • Otherwise, we mark the number as used, append it to path, and recurse forward.
  • When the recursive call returns, we backtrack by removing the number from the end of path and marking it as unused.

The auxiliary space complexity is O(n) due to the recursion stack and the state arrays.

Step-by-Step Execution Walkthrough

Let's trace the backtracking flow for nums = [1, 2, 3]:

1. Step 1 (Root Call): backtrack(path=[], used=[false, false, false]).
   • Iteration i = 0: nums[0] (1) is unused. Mark used[0] = true, path is [1]. Recurse!
2. Step 2 (Recurse Level 1): backtrack(path=[1], used=[true, false, false]).
   • Iteration i = 0: Already used. Skip.
   • Iteration i = 1: nums[1] (2) is unused. Mark used[1] = true, path is [1, 2]. Recurse!
3. Step 3 (Recurse Level 2): backtrack(path=[1, 2], used=[true, true, false]).
   • Iteration i = 0, 1: Already used. Skip.
   • Iteration i = 2: nums[2] (3) is unused. Mark used[2] = true, path is [1, 2, 3]. Recurse!
4. Step 4 (Base Case reached): backtrack(path=[1, 2, 3]).
   • path.size() == 3. Save copy to result. Return.
5. Step 5 (Backtrack from level 2): In Step 3, we unmark used[2] = false, pop 3. Path becomes [1, 2]. Loop ends. Return.
6. Step 6 (Backtrack from level 1): In Step 2, we unmark used[1] = false, pop 2. Path becomes [1].
   • Loop in Step 2 continues to i = 2. nums[2] (3) is unused. Mark used[2] = true, path becomes [1, 3]. Recurse!
   • This path will eventually complete to [1, 3, 2], save it, and backtrack.
7. Step 7 (Explore other roots): The algorithm backtracks to the root and initiates scans starting with 2 and 3, exploring all paths.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• boolean[] used: A high-performance lookup state. Using a boolean array reduces lookup time to O(1), optimizing the overall runtime.
• if (used[i]) continue;: The pruning check. Skips characters that are already active in the current path.
• used[i] = true; path.add(nums[i]); ... used[i] = false; path.remove(path.size() - 1);: The classic choose-explore-unchoose cycle, restoring state for adjacent branches.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

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

public class Permutations {

    // Backtracking Search: Time O(N * N!), Space O(N)
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        boolean[] used = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), used, result);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        // Base case: if current path contains all numbers, a permutation is complete
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // Must deep copy
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // Skip elements that are already in our current path
            if (used[i]) {
                continue;
            }

            // 1. Choose: Mark as used and add to path
            used[i] = true;
            path.add(nums[i]);

            // 2. Explore: Recurse to generate subsequent positions
            backtrack(nums, path, used, result);

            // 3. Unchoose: Backtrack by removing and marking unused
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Permutations solver = new Permutations();
        int[] nums = {1, 2, 3};

        System.out.println("--- Permutations Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));
        List<List<Integer>> list = solver.permute(nums);
        System.out.println("All Permutations: " + list);
    }
}

Conclusion

Generating permutations requires exploring all possible orderings of a set. By utilizing backtracking and optimizing lookup operations with a used state array, we navigate the state space tree with maximum execution speed and minimum memory overhead.