Understanding Permutations in Java

What We're Solving & Order Variations

Generating all distinct orderings of a set of elements is a fundamental problem in combinatorial computing. The Permutations problem asks us to construct every possible arrangement or sequence of a collection of distinct integers, nums.

A permutation represents a specific linear layout of elements. For a set of size n, the total count of unique arrangements is exactly n! (n factorial). For instance, given the array nums = [1, 2, 3], the solution comprises 3! = 6 unique lists:

• [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

Finding all permutations requires exploring a state space tree of size O(n!). Using recursive backtracking alongside a lookup buffer to check visited elements is the standard, most efficient way to solve this.

The Strategy

Backtracking with Used-State Pruning (O(n * n!) Time, O(n) Space)

Let's look at the recursive pointer mechanics of this O(n * n!) runtime algorithm:

• Path Building: We construct a single candidate path list (path) recursively, adding numbers one-by-one.
• Base Case: When the length of path matches nums.length, we have successfully formed a complete arrangement. We create a copy of the path and add it to our final results list.
• State Checking: At each step, we iterate through all elements in nums. To ensure we do not reuse elements, we maintain a boolean array used, where used[i] tracks whether nums[i] is currently active in our path. This lookup is a constant-time O(1) operation, which is significantly faster than using path.contains(num) (which runs in linear O(n) time).
• Backtrack Phase: If the current element is unused, we mark it as used (used[i] = true), append it to path, and recurse forward. Once that search branch completes, we revert our changes by removing the element from the end of path and marking it as unused (used[i] = false). This restores the correct state for neighboring search branches.

Detailed Trace Walkthrough

Let's trace this backtracking search step-by-step on nums = [1, 2, 3]:

1. Step 1 (Root Call): We execute backtrack(path=[], used=[false, false, false]).
   • Index i = 0: Value 1 is unused. We set used[0] = true, update path = [1], and recurse.
2. Step 2 (Recurse Level 1): We execute backtrack(path=[1], used=[true, false, false]).
   • Index i = 0: Already used, so we skip it.
   • Index i = 1: Value 2 is unused. We set used[1] = true, update path = [1, 2], and recurse.
3. Step 3 (Recurse Level 2): We execute backtrack(path=[1, 2], used=[true, true, false]).
   • Index i = 0, 1: Already used, so we skip them.
   • Index i = 2: Value 3 is unused. We set used[2] = true, update path = [1, 2, 3], and recurse.
4. Step 4 (Base Case): We execute backtrack(path=[1, 2, 3], ...).
   • Since path.size() == 3, we save a copy of the path. Results: [[1, 2, 3]]. We return to the caller.
5. Step 5 (Backtrack from Level 2):
   • We set used[2] = false and pop 3 from path → path = [1, 2]. The loop ends, and we return.
6. Step 6 (Backtrack from Level 1):
   • We set used[1] = false and pop 2 from path → path = [1].
   • The loop continues to index i = 2. Value 3 is unused. We set used[2] = true, update path = [1, 3], and recurse.
   • This path will eventually complete to [1, 3, 2], save it, and backtrack.
7. Step 7 (Exploring Other Roots):
   • The algorithm backtracks all the way to the root and starts the next iterations with values 2 and 3, discovering the remaining permutations.

Code Highlights & Explanations

Key highlights of our Java implementation:

• boolean[] used serves as a fast state-checking buffer to avoid expensive list lookups.
• result.add(new ArrayList<>(path)) makes a deep copy of the path, ensuring that subsequent backtrack modifications do not mutate previously recorded solutions.

Full Code Solution

Below is the complete, self-contained Java source code demonstrating this backtracking strategy, along with a main method for printing the generated combinations.

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 & Takeaways

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.