Algorithms

Backtracking: The Art of Exploring Every Possibility

May 2026
8 min read

When a problem asks you to generate 'all possible combinations', 'all permutations', or 'all valid subsets', there is no shortcut. You must explore the entire state space. Backtracking is the disciplined way to do this without getting lost.

Introduction

Backtracking is essentially a highly structured Depth-First Search (DFS). It is used when we need to find all (or some) solutions to a computational problem that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly lead to a valid solution.

Think of it like navigating a massive maze. You walk down a path until you hit a dead end. When you hit the dead end, you don't teleport back to the start. You take a step back to the previous intersection, mark the dead-end path as bad, and try the next hallway.

The Three Steps of Backtracking

Every standard backtracking algorithm follows the exact same three-step physical rhythm:

  1. Make a Choice: Add an element to your temporary list.
  2. Explore: Recursively call your backtrack function to see where this choice leads.
  3. Undo the Choice: Remove the element you just added, returning the state to exactly how it was before step 1, so the loop can try the next possible choice.

Example: Generating Subsets (LeetCode #78)

Given an array [1, 2, 3], we want to find every possible subset.

  1. We start with an empty list []. We add it to our results.
  2. Our loop starts at 1. We add 1 to our list. State: [1]. We recursively explore.
  3. Inside the recursion, we add 2. State: [1, 2]. Explore.
  4. Add 3. State: [1, 2, 3]. Explore. Loop finishes.
  5. The Backtrack: The recursion unrolls. We remove 3. State goes back to [1, 2].
  6. The loop for [1, 2] finishes. We backtrack again. Remove 2. State goes back to [1].
  7. The loop for [1] continues to the next number, which is 3. We add 3. State: [1, 3].

We systematically build, record, and tear down our state.

Why the "Undo" step is critical

In Java (and most languages), objects like ArrayList are passed by reference. If we don't remove the element after exploring it, the elements will just keep piling up into a single massive, incorrect list.

By adding, exploring, and removing, we keep a single, clean memory allocation that acts as a flexible workspace for the entire recursion tree.

  • Time Complexity: $O(N \times 2^N)$ — For a set of size N, there are $2^N$ possible subsets, and we spend $O(N)$ time copying each subset into the result array.
  • Space Complexity: $O(N)$ — The maximum depth of our recursion call stack.

Implementation

java
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), nums, 0); return result; } private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) { // Add the current subset to our final result result.add(new ArrayList<>(tempList)); for (int i = start; i < nums.length; i++) { // Make a choice tempList.add(nums[i]); // Explore that choice backtrack(result, tempList, nums, i + 1); // UNDO the choice (Backtrack) tempList.remove(tempList.size() - 1); } } }