Backtracking Pattern in Java: Permutations and Combinations

Introduction to Backtracking

Backtracking is a general algorithmic technique for solving problems that incrementally build candidates to the solutions and abandon a candidate ("backtrack") as soon as it determines that the candidate cannot possibly be completed to a valid solution. It is often used for problems that involve searching for all (or some) solutions to a computational problem, particularly constraint satisfaction problems and combinatorial optimization problems.

Think of backtracking as exploring a decision tree. At each node, you make a choice. If that choice leads to a dead end (violates constraints or cannot form a solution), you undo that choice and try another path. This process continues until a solution is found or all possibilities are exhausted.

When Should You Think About Backtracking?

Consider using Backtracking when:

• You need to find all possible solutions (or a specific number of solutions) to a problem.
• The problem involves making a sequence of choices.
• There are constraints that can prune the search space early.
• Problems involve permutations, combinations, subsets, Sudoku solving, N-Queens, Hamiltonian cycles, etc.

Core Concepts of Backtracking

The general structure of a backtracking algorithm involves a recursive function that takes the current state of the solution as input. Inside this function:

1. Base Case: Check if the current state is a complete and valid solution. If so, record it and return.
2. Explore Choices: Iterate through all possible choices that can be made from the current state.
3. Make a Choice: Apply a choice, updating the current state.
4. Recurse: Call the backtracking function with the new state.
5. Undo Choice (Backtrack): After the recursive call returns, undo the choice made in step 3. This is crucial to explore other paths in the decision tree.

We will illustrate this with two classic combinatorial problems: Permutations and Combinations.

1. Generating Permutations

A permutation is an arrangement of all or part of a set of items. The order of items matters. For a set of n distinct items, there are n! (n factorial) possible permutations.

Example: Permutations of an Array

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrackPermute(nums, new ArrayList<>(), result, new boolean[nums.length]);
        return result;
    }

    private void backtrackPermute(
        int[] nums,
        List<Integer> currentPermutation,
        List<List<Integer>> result,
        boolean[] used
    ) {
        // Base Case: If the current permutation is complete
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation)); // Add a copy
            return;
        }

        // Explore Choices: Iterate through all available numbers
        for (int i = 0; i < nums.length; i++) {
            // If the number has not been used yet
            if (!used[i]) {
                // Make a Choice: Add the number to the current permutation
                currentPermutation.add(nums[i]);
                used[i] = true; // Mark as used

                // Recurse: Explore further permutations
                backtrackPermute(nums, currentPermutation, result, used);

                // Undo Choice (Backtrack): Remove the number and mark as unused
                currentPermutation.remove(currentPermutation.size() - 1);
                used[i] = false;
            }
        }
    }
}

Complexity:

• Time Complexity: O(N * N!), where N is the number of elements. There are N! permutations, and for each permutation, we perform N operations (adding to currentPermutation).
• Space Complexity: O(N) for the currentPermutation list and the used array, plus O(N) for the recursion stack depth.

Dry Run: Permutations

Input: nums = [1, 2, 3]

Final Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

2. Generating Combinations

A combination is a selection of items from a set where the order of selection does not matter. For a set of n distinct items, choosing k items, there are C(n, k) (n choose k) possible combinations.

Example: Combinations of K elements

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

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

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrackCombine(n, k, 1, new ArrayList<>(), result);
        return result;
    }

    private void backtrackCombine(
        int n,
        int k,
        int start,
        List<Integer> currentCombination,
        List<List<Integer>> result
    ) {
        // Base Case: If the current combination has k elements
        if (currentCombination.size() == k) {
            result.add(new ArrayList<>(currentCombination)); // Add a copy
            return;
        }

        // Optimization: If remaining elements are not enough to form a combination of size k
        // (n - start + 1) is the number of remaining elements from 'start' to 'n'
        // k - currentCombination.size() is the number of elements still needed
        if (n - start + 1 < k - currentCombination.size()) {
            return;
        }

        // Explore Choices: Iterate from 'start' to 'n'
        for (int i = start; i <= n; i++) {
            // Make a Choice: Add the number to the current combination
            currentCombination.add(i);

            // Recurse: Explore further combinations, starting from the next number (i + 1)
            backtrackCombine(n, k, i + 1, currentCombination, result);

            // Undo Choice (Backtrack): Remove the number
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

Complexity:

• Time Complexity: O(C(N, K) * K), where C(N, K) is the number of combinations (N! / (K! * (N-K)!)). For each combination, we perform K operations (adding to currentCombination). The pruning step helps reduce the constant factor but doesn't change the worst-case complexity.
• Space Complexity: O(K) for the currentCombination list and O(K) for the recursion stack depth.

Dry Run: Combinations

Input: n = 4, k = 2

backtrackCombine(4, 2, 1, [], [])

• i = 1: currentCombination = [1]
  • backtrackCombine(4, 2, 2, [1], [])
    • i = 2: currentCombination = [1,2] -> result.add([1,2])
    • currentCombination = [1] (backtrack 2)
    • i = 3: currentCombination = [1,3] -> result.add([1,3])
    • currentCombination = [1] (backtrack 3)
    • i = 4: currentCombination = [1,4] -> result.add([1,4])
    • currentCombination = [1] (backtrack 4)
  • currentCombination = [] (backtrack 1)
• i = 2: currentCombination = [2]
  • backtrackCombine(4, 2, 3, [2], [[1,2],[1,3],[1,4]])
    • i = 3: currentCombination = [2,3] -> result.add([2,3])
    • currentCombination = [2] (backtrack 3)
    • i = 4: currentCombination = [2,4] -> result.add([2,4])
    • currentCombination = [2] (backtrack 4)
  • currentCombination = [] (backtrack 2)
• i = 3: currentCombination = [3]
  • backtrackCombine(4, 2, 4, [3], [[1,2],[1,3],[1,4],[2,3],[2,4]])
    • i = 4: currentCombination = [3,4] -> result.add([3,4])
    • currentCombination = [3] (backtrack 4)
  • currentCombination = [] (backtrack 3)

Final Result: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Reusable Template for Backtracking

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

class BacktrackingTemplates {

    // --- Permutations (Distinct Elements) ---
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        backtrackPermute(nums, new ArrayList<>(), result, new boolean[nums.length]);
        return result;
    }

    private void backtrackPermute(
        int[] nums,
        List<Integer> currentPermutation,
        List<List<Integer>> result,
        boolean[] used
    ) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                currentPermutation.add(nums[i]);
                used[i] = true;
                backtrackPermute(nums, currentPermutation, result, used);
                used[i] = false;
                currentPermutation.remove(currentPermutation.size() - 1);
            }
        }
    }

    // --- Combinations ---
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (k <= 0 || k > n) {
            return result;
        }
        backtrackCombine(n, k, 1, new ArrayList<>(), result);
        return result;
    }

    private void backtrackCombine(
        int n,
        int k,
        int start,
        List<Integer> currentCombination,
        List<List<Integer>> result
    ) {
        if (currentCombination.size() == k) {
            result.add(new ArrayList<>(currentCombination));
            return;
        }

        // Optimization: Prune if not enough elements left to form a combination
        // (n - i + 1) is the number of remaining elements from 'i' to 'n'
        // k - currentCombination.size() is the number of elements still needed
        // The loop should go up to n - (k - currentCombination.size()) + 1
        // For example, if n=4, k=2, currentCombination.size()=0, need 2 elements.
        // Loop should go up to 4 - (2-0) + 1 = 3. So i can be 1, 2, 3.
        // If i=3, currentCombination=[3], need 1 element. Loop for next call starts at 4.
        // n - i + 1 >= k - currentCombination.size()
        for (int i = start; i <= n - (k - currentCombination.size()) + 1; i++) {
            currentCombination.add(i);
            backtrackCombine(n, k, i + 1, currentCombination, result);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

How to Recognize Backtracking in Interviews

Look for these clues:

• Goal: Find all solutions, count all solutions, or find one optimal solution by exploring all possibilities.
• Problem Type: Combinatorial problems (permutations, combinations, subsets), constraint satisfaction problems (Sudoku, N-Queens), pathfinding in mazes.
• Keywords: "All possible", "find all", "generate all", "arrange", "select", "place", "solve".
• Structure: Often involves a recursive function, a current solution state, and a way to undo choices.

Common Mistakes

Mistake 1: Not Undoing Choices (Forgetting to Backtrack)

This is the most common mistake. If you don't remove the last added element or reset the used state, your subsequent recursive calls will operate on an incorrect state, leading to wrong results or infinite loops.

Mistake 2: Incorrect Base Case

The base case must correctly identify when a valid solution is found and when to stop recursion. For permutations, it's when the currentPermutation size equals N. For combinations, it's when currentCombination size equals K.

Mistake 3: Duplicates in Results (for non-distinct elements)

If the input array contains duplicate elements, the standard permutation/combination algorithms will produce duplicate results. Special handling (e.g., sorting the input and skipping duplicates in the loop) is required for such cases.

Mistake 4: Inefficient Pruning

While backtracking explores all paths, effective pruning (like the optimization in combinations) can significantly reduce the actual number of paths explored, improving performance. Not implementing pruning when possible can lead to Time Limit Exceeded (TLE).

Backtracking vs. Other Algorithmic Paradigms

• Dynamic Programming (DP): DP is used when subproblems overlap and an optimal substructure exists. Backtracking explores all paths, often without overlapping subproblems in the same way DP does, and is typically for finding all solutions rather than just an optimal value.
• Greedy Algorithms: Greedy algorithms make locally optimal choices in the hope of finding a global optimum. Backtracking explores all choices, making it suitable when a greedy approach might miss the optimal solution.
• BFS/DFS: Backtracking is essentially a form of DFS. The key difference is the explicit "undo" step (backtracking) to explore alternative paths from a previous state.

Practice Problems for This Pattern

1. Permutations (LeetCode 46) - Generate all permutations of distinct numbers.
2. Permutations II (LeetCode 47) - Generate all unique permutations of numbers that may contain duplicates.
3. Combinations (LeetCode 77) - Generate all combinations of k numbers from [1, n].
4. Combination Sum (LeetCode 39) - Find all unique combinations that sum up to a target.
5. Subsets (LeetCode 78) - Generate all possible subsets of a set.
6. N-Queens (LeetCode 51) - Place N queens on an N×N chessboard.
7. Sudoku Solver (LeetCode 37) - Solve a Sudoku puzzle.

Interview Script You Can Reuse

"This problem requires finding all possible arrangements/selections, which suggests a backtracking approach. I'll define a recursive helper function that takes the current state of our solution. The base case will be when a complete and valid solution is formed, at which point I'll add it to my results. In the recursive step, I'll iterate through all possible choices. For each choice, I'll 'make' it (add to current solution, update state), then recursively call the function. Crucially, after the recursive call returns, I'll 'undo' the choice (backtrack) to explore other possibilities. This ensures all paths in the decision tree are explored. For permutations, I'll use a `used` array to track elements. For combinations, I'll use a `start` index to avoid duplicates and ensure elements are chosen in increasing order. The time complexity will generally be exponential, reflecting the nature of combinatorial problems, and space complexity will be proportional to the depth of the recursion."

Final Takeaways

• Backtracking is a powerful technique for exploring all possible solutions.
• It involves making choices, recursing, and undoing choices.
• Key for permutations, combinations, subsets, and constraint satisfaction problems.
• Pruning (optimizations) can significantly improve performance.
• Always remember to backtrack (undo the choice) to ensure correctness.

Mastering backtracking is essential for tackling a wide range of combinatorial and search problems in algorithms and interviews.

Read Next

• DSA in Java Series
• N-Queens Problem in Java
• Sudoku Solver in Java
• Word Search in Java
• Subset Sum and Partition Problems in Java
• Bellman-Ford Algorithm in Java
• Kruskal’s Algorithm in Java
• Prim’s Algorithm in Java
• Matrix Traversal in Java
• Lowest Common Ancestor (LCA) in Java
• Dijkstra’s Algorithm in Java
• Union Find (DSU) in Java
• Topological Sort in Java
• BFS (Breadth First Search) in Java
• DFS (Depth First Search) in Java
• Monotonic Queue Pattern in Java
• Monotonic Stack Pattern in Java
• Sorting Algorithms in Java
• Binary Search Pattern in Java
• In-place Reversal of a Linked List in Java
• Fast & Slow Pointers in Java
• Dutch National Flag Pattern in Java
• Kadane’s Algorithm in Java
• Prefix Sum Pattern in Java
• Sliding Window Pattern in Java
• Two Pointers Pattern in Java
• Big-O Notation in Java