Permutations: backtracking with a used[] array

• Depth-first backtracking – at each position, choose an element not yet used in the current path.
• used[] array – a boolean array tracking which elements are currently placed.
• Record at full length – when the path size equals n, snapshot it as a complete permutation.
• Undo on backtrack – remove the element and unmark used[] before trying the next candidate.
• **O(n * n!)** – n! permutations, each requiring O(n) to copy.

What is the problem?

Given an array of distinct integers, return all possible orderings. In a banking context, Pankaj at National Bank of India needs to evaluate every possible execution order of a small set of settlement batches to assess order-dependent risk.

How does the used[] backtracking work?

Carry a path list and a used[] boolean array. When the path size equals n, record a copy. Otherwise loop over all indices, skip used ones, add the element (mark used), recurse, then undo.

package com.bank.service;

import java.util.*;

public class BatchOrderEvaluator {

    public static List<List<String>> allPermutations(String[] batches) {
        List<List<String>> result = new ArrayList<>();
        boolean[] used = new boolean[batches.length];
        backtrack(batches, used, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(String[] batches, boolean[] used,
            List<String> path, List<List<String>> result) {
        if (path.size() == batches.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < batches.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(batches[i]);
            backtrack(batches, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        String[] batches = {"Interest", "Fees", "Notify"};
        List<List<String>> orders = allPermutations(batches);
        System.out.println("All orderings (" + orders.size() + "):");
        for (List<String> order : orders) {
            System.out.println("  " + order);
        }
    }
}

All orderings (6):
  [Interest, Fees, Notify]
  [Interest, Notify, Fees]
  [Fees, Interest, Notify]
  [Fees, Notify, Interest]
  [Notify, Interest, Fees]
  [Notify, Fees, Interest]

How is this different from subsets?

In subsets, a start index restricts choices to elements after the current one, producing combinations. In permutations, there is no start index: every position draws from any unused element, producing orderings.

| Aspect | Subsets | Permutations |
|---|---|---|
| Start index | Yes (i + 1) | No (always 0) |
| Record when | Every node | Only at full length |
| Count | 2^n | n! |
| Tracking | Start index | used[] array |

What is the swap-based alternative?

Instead of a used[] array, swap the current element into position, recurse, then swap back. This avoids the extra boolean array but makes the code less intuitive.

private static void backtrackSwap(String[] batches, int start,
        List<List<String>> result) {
    if (start == batches.length) {
        result.add(Arrays.asList(batches.clone()));
        return;
    }
    for (int i = start; i < batches.length; i++) {
        swap(batches, start, i);
        backtrackSwap(batches, start + 1, result);
        swap(batches, start, i);
    }
}

What is the time and space complexity?

• **Time: O(n * n!)** because there are n! permutations and copying each costs O(n).
• Space: O(n) for the recursion depth and used[] array (excluding output).

What are common mistakes?

The most common mistake is forgetting to unmark used[i] after the recursive call, which causes missing permutations. Another is using a start index like subsets, which would produce combinations instead of permutations.

// Wrong: forgetting to unmark
used[i] = true;
path.add(batches[i]);
backtrack(...);
path.remove(path.size() - 1);
// missing: used[i] = false;

// Correct: always undo both actions
path.remove(path.size() - 1);
used[i] = false;

How does this extend to permutations with duplicates?

When the input contains duplicates, sort the array first and skip a candidate if it equals the previous candidate and the previous candidate is not currently used. This avoids generating duplicate orderings.

What should a senior engineer know?

A senior engineer knows that n! grows extremely fast, so this approach is only practical for small n (typically n <= 10). For larger inputs, the problem must be reformulated to avoid full enumeration. The swap-based variant uses O(1) extra space (excluding output) by modifying the array in place, but it is harder to adapt for duplicate handling.