Articles

Blogs

MCQ

SQL

Q&A

Tools

Tags

Jobs

News

Community

LogIn

Email

Password

Show Password

Forget Password

I don't have account.Sign Up!

Login

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

Adℹ

✕

Backtracking for Beginners: The Complete Guide from Basics to Advanced Patterns

CodeWarlord

Last Updated : 13 August 2026

214 Views

#backtracking

#dsa

#coding-principles

#interview-preparation-tips

#coding-interview

#coding-pattern

#algorithm-pattern

#programming-pattern

#dsa-pattern

#problem-solving-strategy

Adℹ

The first time I saw a backtracking problem in an interview, I remember writing a solution that technically worked, but it took me nearly the whole 45 minutes and I couldn't explain why it worked. I had basically copied the shape of a solution I'd seen before and hoped the interviewer wouldn't ask me to explain it. He did. I fumbled.

Years later, sitting on the other side of the table, I see this exact same thing happen almost every week. Someone writes a backtracking solution that passes, but the moment I ask "why did you undo that step after the recursive call," they go quiet. That line : the "undo" line, is the entire idea of backtracking and if you don't understand why it's there, you haven't actually learned backtracking, you've just memorized a shape.

This article is going to slow down on that exact point. Backtracking is not a scary, advanced topic. It's something you already do naturally, think about solving a maze with a pencil. you walk down a path and the moment you hit a dead end, you don't throw away the paper, you just erase your last few steps and try a different direction from the last place you had a choice. That's it. That's backtracking. Everything else in this article is just teaching you to do that "erase and try again" step in code, cleanly and reliably, on any problem.

What Backtracking Actually Is

Backtracking is a way of exploring every possible option for a problem, but doing it smartly. you build a solution one small decision at a time and the moment you realize a path can't possibly lead anywhere good, you step back and try a different decision instead of continuing down a path you already know is wrong.

Here's a real-life comparison that helps this click for most people. Imagine you're trying to find your way out of a real hedge maze. At every junction, you pick a direction and keep walking. If you hit a dead end, you don't teleport back to the entrance and start completely over. you just walk back to the last junction where you had another unexplored option and try that one instead. You keep doing this until you either find the exit or you've genuinely tried every path from every junction. That walking-back step is backtracking and the reason it's efficient compared to "start completely over each time" is that you're reusing all the walking you already did to reach that junction.

In code, this shows up as recursion with one small but important extra habit, after you try a choice and explore where it leads, you undo that choice before trying the next one so that every branch of your exploration starts from a clean, honest state, exactly like standing back at that junction with no memory of which direction you tried last.

Choose, Explore, Unchoose : The Core Idea

Nearly every backtracking solution, no matter how different the problems look on the surface, follows the same three-step rhythm:

• Choose : pick one option out of the available choices at this step and add it to your current, in-progress solution.
• Explore : recursively continue building the rest of the solution, now that this choice has been made.
• Unchoose : remove that choice from your current solution before trying the next available option, so the next attempt starts fresh, unaffected by the choice you just tried.

That third step, "unchoose," is the one beginners forget most often and it's also the one that actually gives backtracking its name. you're literally tracking back to where you were before you made a choice, so you can try a different one. Skip it and your current, in-progress solution slowly turns into a mess that mixes leftover pieces from choices you already abandoned, which produces wrong answers in a way that's genuinely confusing to debug, because the code doesn't crash. it just quietly gives you garbage.

Let's make this concrete with something almost childishly simple: listing every possible outfit from 2 shirts and 2 pants.

• Choose shirt A → choose pants X → we have outfit (A, X), record it → unchoose pants X
• Choose pants Y → outfit (A, Y), record it → unchoose pants Y
• Unchoose shirt A
• Choose shirt B → choose pants X → outfit (B, X), record it → unchoose pants X
• Choose pants Y → outfit (B, Y), record it → unchoose pants Y
• Unchoose shirt B

Notice how "unchoose shirt A" happens right before we move on to shirt B if we skipped it, shirt A would still be sitting in our current outfit when we tried to add shirt B and we'd end up with a broken combination. This tiny outfit example has no real complexity to it, but it contains 100% of the logic that powers every backtracking problem in this article, including the hard ones later on.

Backtracking vs Brute Force vs Dynamic Programming

These three get mixed up a lot, so let's separate them clearly, because knowing which one a problem actually needs saves you from forcing the wrong tool onto it.

	Brute Force	Backtracking	Dynamic Programming
What it does	Tries every possibility, often by generating them all upfront	Tries possibilities one decision at a time, abandoning bad paths early	Breaks a problem into smaller subproblems and reuses their answers
Typical output	Usually one best answer, checked against everything	Usually all valid answers or existence of one	Usually a single best number (max, min, count)
Repeats work?	Often yes, with no reuse at all	Avoids exploring paths that are already known to be dead ends	Avoids recalculating the same subproblem twice
Good fit when	The problem space is tiny and simplicity matters most	You need every valid combination/arrangement or one that satisfies constraints	The same smaller subproblem is asked for repeatedly and you want an optimal value

Here's a genuinely useful way to remember the difference between backtracking and DP specifically, since these two get confused the most: DP is for questions like "what's the best score," and backtracking is for questions like "show me every valid way." If a problem asks you to generate all subsets, all permutations, all valid board arrangements or all paths that satisfy some rule that's backtracking's territory, not DP's, because DP is built around avoiding repeated identical subproblems and most backtracking problems don't actually revisit the exact same state twice in the first place.

The Universal Backtracking Template

Here is the shape I use for genuinely every backtracking problem I solve and it's worth memorizing this structure, not because memorizing is the goal, but because once this shape is second nature, your energy goes entirely into the problem-specific parts instead of the plumbing around them.

void backtrack(State currentState, Choices remainingChoices, Result result) {
    if (isGoalReached(currentState)) {
        recordSolution(currentState, result);
        return; // or don't return, if you want to keep exploring further too
    }

    for (Choice choice : remainingChoices) {
        if (!isValid(choice, currentState)) {
            continue; // skip choices that break the problem's rules
        }

        makeChoice(choice, currentState);      // Choose
        backtrack(currentState, updatedChoices, result); // Explore
        undoChoice(choice, currentState);      // Unchoose
    }
}

Every single worked example in this article is this exact same skeleton, with the four blanks : isGoalReached, isValid, makeChoice, undoChoice : filled in differently depending on the problem. Once you see this pattern repeat across six genuinely different-looking problems, you'll stop seeing backtracking as "a bunch of separate tricky problems" and start seeing it as one idea wearing different outfits.

Worked Example 1 : Subsets

The problem: Given an array of distinct numbers, return every possible subset (including the empty set and the full set itself). Example: [1, 2, 3] should produce [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

The way to think about this, at every number in the array, you genuinely have a binary decision, include it in the current subset or don't. Backtracking explores this by walking through the array once and at each position, trying "include" and then, after exploring everything that follows, trying "don't include."

import java.util.*;
public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    private static void backtrack(int[] nums, int start, List<Integer> current,
                                    List<List<Integer>> result) {
        // every state we reach, even a partial one, is itself a valid subset
        result.add(new ArrayList<>(current));
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);                 // Choose
            backtrack(nums, i + 1, current, result); // Explore
            current.remove(current.size() - 1);    // Unchoose
        }
    }
}

Notice something a bit different here compared to the outfit example : we record the answer at every call, not just at the "end" of the recursion, because in this particular problem, every partial combination we build along the way is itself a valid, complete subset. This is a small but important detail: where exactly you record your answer depends entirely on what counts as a "finished" solution for that specific problem and it's the first thing to figure out before writing any code.

A quick trace on [1, 2]: start with current = [], record []. Then choose 1 → current = [1], record [1]. Then choose 2 → current = [1, 2], record [1, 2]. Unchoose 2 → back to [1]. Unchoose 1 → back to []. Then choose 2 → current = [2], record [2]. Unchoose 2 → back to [], loop ends. Final results: [], [1], [1,2], [2] : all four subsets of a 2-element array, exactly as expected.

Worked Example 2 : Permutations

The problem: given an array of distinct numbers, return every possible ordering (permutation) of them. Example: [1, 2, 3] should produce all 6 orderings, like [1,2,3], [1,3,2], [2,1,3] and so on.

This is a genuinely different flavor from subsets here, order matters and every element must be used exactly once in every result. The key extra piece of bookkeeping is a way to know which elements have already been used in the current arrangement, so you don't accidentally reuse one.

import java.util.*;

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

    private static void backtrack(int[] nums, List<Integer> current, boolean[] used,
                                    List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current)); // a full-length arrangement is our goal
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // skip anything already placed in this arrangement

            used[i] = true;
            current.add(nums[i]);                       // Choose
            backtrack(nums, current, used, result);      // Explore
            current.remove(current.size() - 1);          // Unchoose
            used[i] = false;
        }
    }
}

The used array is doing exactly the same job as the visited grid we'll see later in Word Search. it's how backtracking keeps track of "what's already part of my current path," so it never reuses something it shouldn't. This is a pattern worth remembering on its own: whenever a problem says "each item can only be used once," you almost always need some kind of used or visited tracker sitting right next to your recursion.

Worked Example 3 : Combination Sum

The problem: given a set of distinct candidate numbers and a target, find every unique combination of candidates that sums exactly to the target. The same number can be reused as many times as needed. Example: candidates = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]].

This one introduces a genuinely useful new idea, since numbers can repeat, when you "choose" a candidate, you allow the very next recursive call to choose that same candidate again but to avoid producing the same combination in a different order (like both [2,2,3] and [2,3,2]), you only ever look forward from your current position, never backward.

import java.util.*;

public class CombinationSum {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] candidates, int remaining, int start,
                                    List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current)); // hit the target exactly
            return;
        }
        if (remaining < 0) {
            return; // overshot the target, this path is dead
        }
        for (int i = start; i < candidates.length; i++) {
            current.add(candidates[i]);
            // pass 'i', not 'i + 1' : this candidate can be reused again
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
}

That single difference : passing i instead of i + 1 into the recursive call, is the entire trick that allows reuse and it's worth comparing directly against the Permutations example, where every choice moves strictly forward with no repeats allowed. Small details like this one are exactly what separates "understanding backtracking" from "having memorized one specific backtracking solution", the skeleton is identical, but this one line changes the entire behavior of the algorithm.

Tracing candidates = [2, 3, 6, 7], target = 7: choosing 2, 2, 2 overshoots to remaining = 1, then every further candidate overshoots further, so that branch dies without a result. Backing up to 2, 2, 3 gives remaining = 0 exactly : recorded. Backing up further and trying 2, 3 then 3 again overshoots. Eventually the branch starting fresh with 7 alone also hits remaining = 0 recorded. Final result: [[2, 2, 3], [7]], matching the expected output exactly.

Worked Example 4 : Word Search

The problem: given a 2D grid of letters and a target word, determine if the word can be formed by moving to adjacent cells (up, down, left, right), without reusing the same cell twice within one word.

This example moves backtracking from "building a list" to "exploring a grid," which is an extremely common real-world shape, think of how a game character explores a map or how a maze-solving robot decides which direction to try next.

public class WordSearch {
    public static boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (backtrack(board, word, 0, r, c, visited)) {
                    return true; // found a valid starting point that works
                }
            }
        }
        return false;
    }

    private static boolean backtrack(char[][] board, String word, int index,
                                       int row, int col, boolean[][] visited) {
        if (index == word.length()) {
            return true; // matched every character of the word
        }
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return false; // walked off the grid
        }
        if (visited[row][col] || board[row][col] != word.charAt(index)) {
            return false; // already used or letter doesn't match
        }

        visited[row][col] = true; // Choose

        // Explore all four directions
        boolean found = backtrack(board, word, index + 1, row + 1, col, visited)
                      || backtrack(board, word, index + 1, row - 1, col, visited)
                      || backtrack(board, word, index + 1, row, col + 1, visited)
                      || backtrack(board, word, index + 1, row, col - 1, visited);

        visited[row][col] = false; // Unchoose : this cell might work for a different path later
        return found;
    }
}

The visited grid is undone (visited[row][col] = false) right before returning, regardless of whether this particular path found the word or not. This matters because a cell that didn't work as part of this attempted path might still work perfectly fine as part of a different path starting somewhere else on the grid and if you forgot to unmark it, you'd wrongly treat that cell as permanently unusable for the rest of the search.

Worked Example 5 : Palindrome Partitioning

The problem: given a string, split it into pieces such that every single piece is a palindrome and return every possible way to do this. Example: "aab" → [["a","a","b"], ["aa","b"]].

This example introduces a new kind of choice, instead of picking one item from a list, you're picking where to cut the string next.

import java.util.*;

public class PalindromePartitioning {
    public static List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(String s, int start, List<String> current,
                                    List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(current)); // used up the whole string
            return;
        }

        for (int end = start + 1; end <= s.length(); end++) {
            String piece = s.substring(start, end);
            if (isPalindrome(piece)) {
                current.add(piece);                        // Choose this cut
                backtrack(s, end, current, result);         // Explore from here
                current.remove(current.size() - 1);          // Unchoose
            }
            // if it's not a palindrome, we simply skip it : no need to explore further
        }
    }

    private static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

Notice the if (isPalindrome(piece)) check sitting right before we choose to explore that cut. this is our first real look at pruning, which is worth its own dedicated section next, because it's the single biggest reason backtracking is usable at all on anything beyond tiny inputs.

Worked Example 6 : N-Queens

The problem: place n queens on an n x n chessboard so that no two queens attack each other, meaning no two queens share a row, a column or a diagonal. Count (or list) all valid arrangements.

This is the example I use to show people that backtracking scales up to genuinely hard-looking problems using the exact same skeleton as the outfit example from Section 2 : nothing new conceptually, just more careful bookkeeping about what counts as "valid."

Since we place one queen per row, we only ever need to decide which column each row's queen goes in, which already eliminates the "same row" conflict for free. We track used columns and used diagonals directly, so checking validity is fast.

public class NQueens {
    public static int totalNQueens(int n) {
        boolean[] usedCols = new boolean[n];
        boolean[] usedDiag1 = new boolean[2 * n]; // identified by (row + col)
        boolean[] usedDiag2 = new boolean[2 * n]; // identified by (row - col + n)
        return backtrack(0, n, usedCols, usedDiag1, usedDiag2);
    }

    private static int backtrack(int row, int n, boolean[] usedCols,
                                   boolean[] usedDiag1, boolean[] usedDiag2) {
        if (row == n) {
            return 1; // successfully placed a queen in every row : one valid arrangement
        }

        int count = 0;
        for (int col = 0; col < n; col++) {
            int diag1 = row + col;
            int diag2 = row - col + n;

            if (usedCols[col] || usedDiag1[diag1] || usedDiag2[diag2]) {
                continue; // this column or diagonal is already under attack, skip it
            }

            usedCols[col] = usedDiag1[diag1] = usedDiag2[diag2] = true;   // Choose
            count += backtrack(row + 1, n, usedCols, usedDiag1, usedDiag2); // Explore
            usedCols[col] = usedDiag1[diag1] = usedDiag2[diag2] = false;  // Unchoose

        }
        return count;
    }
}

For n = 4, this correctly returns 2, matching the two well-known valid arrangements for a 4x4 board. The diagonal tracking is the only genuinely new idea here, every cell along the same "downward-right" diagonal shares the same value of row - col and every cell along the same "downward-left" diagonal shares the same value of row + col. That's a small piece of math worth sitting with on paper for a minute, but once it clicks, it unlocks a whole family of grid and board-based backtracking problems.

Pruning : Cutting Off Bad Branches Early

Pruning is what separates a backtracking solution that finishes in a fraction of a second from one that technically works but takes forever on anything but the tiniest input. The idea is simple: the moment you can tell a partial solution has no chance of leading anywhere valid, stop exploring it immediately, instead of continuing on and discovering the failure later.

You've actually already seen pruning multiple times in this article, without me naming it yet:

• In Combination Sum, the line if (remaining < 0) return; prunes away any path the instant it overshoots the target. there's no reason to keep adding more numbers to a sum that's already too big.
• In Palindrome Partitioning, only exploring further when isPalindrome(piece) is true prunes away every cut that couldn't possibly lead to a valid full partition.
• In N-Queens, checking usedCols, usedDiag1 and usedDiag2 before placing a queen prunes away placements that are already guaranteed to conflict, rather than placing the queen and discovering the conflict several rows later.

The general lesson: look for a check you can perform right now, before going deeper, that would let you skip an entire branch of possibilities in one move. Every real pruning check follows this same shape "is there any way this partial attempt could possibly succeed? If clearly not, stop right here." Getting good at spotting these checks is genuinely most of what separates a slow backtracking solution from a fast one, far more than any clever data structure.

Common Patterns You'll See Again and Again

Once you've solved enough backtracking problems, you start noticing they cluster into a small number of recurring shapes. Here they are, described by their thought process rather than their names, since recognizing the shape matters more than the label:

• Include-or-exclude problems (like Subsets) : at every element, you have exactly two choices: take it or skip it. The decision tree naturally branches into two at every step.
• Fixed-length arrangement problems (like Permutations) : every element must be used exactly once, order matters and you need a used tracker to avoid repeats.
• Unlimited-reuse combination problems (like Combination Sum) : elements can be reused, so your recursive call moves forward from the current position rather than the next one.
• Grid or graph exploration problems (like Word Search) : you move between neighboring positions, need a visited tracker for the current path and often explore in multiple directions from each cell.
• String-splitting problems (like Palindrome Partitioning) : instead of choosing from a fixed list, you're choosing where to make the next cut in a string.
• Constraint satisfaction / board problems (like N-Queens and Sudoku solvers built the same way) : you place items one at a time onto a structure while tracking several overlapping rules (rows, columns, diagonals, boxes), pruning aggressively whenever a rule would be broken.

If a new problem doesn't cleanly match one of these, don't panic, most real backtracking problems are actually a small combination of two of these shapes stitched together, like a grid-exploration problem that also involves a used-once constraint or a combination problem with an extra include/exclude rule layered on top.

How to Spot a Backtracking Problem

The honest signals I look for, the same ones worth training yourself to notice:

• The question asks for all possible results : all subsets, all permutations, all valid arrangements, all paths, not just a single best number.
• The question asks whether at least one valid arrangement exists and satisfying it requires trying different combinations of choices, like Word Search or Sudoku.
• Choices made earlier in the problem genuinely restrict what choices are available later, placing a queen affects which columns remain safe, using a letter in a grid affects which cells are still available.
• Brute-force "try everything" would technically work but is clearly wasteful, because many partial attempts can be abandoned early once you notice they've already broken a rule.

If a question instead asks for a single maximum, minimum or count derived from overlapping smaller versions of the exact same subproblem, that's more likely pointing you toward Dynamic Programming, as covered in the previous article in this series : it's genuinely worth reading both, because the overlap and contrast between the two topics helps both of them stick better in your memory.

Common Mistakes Beginners Make

• Forgetting the "unchoose" step, which quietly corrupts your current state across different branches and produces confusing, wrong output without ever throwing an error.
• Copying a list by reference instead of creating a new copy when recording a result : writing result.add(current) instead of result.add(new ArrayList<>(current)). Since current keeps changing as the recursion continues, every entry you added earlier ends up pointing to the same, now-different list and your final results all end up looking wrong or identical.
• Not pruning early enough, which technically still produces the correct answer but can make an otherwise reasonable solution painfully slow on larger inputs.
• Confusing "used" tracking between problems that allow reuse and problems that don't : using i + 1 when a problem actually allows reuse or using i when it doesn't, silently changes the entire meaning of your solution.
• Not clearly defining what counts as a "complete" solution before coding. In Subsets, every partial state is already complete. In Permutations, only a full-length arrangement counts. Mixing these up leads to either missing results or way too many incorrect ones.
• Trying to solve grid problems without a visited tracker, which usually causes infinite loops as the recursion walks back and forth between the same two cells forever.

Practice Questions by Pattern

Rather than one long undifferentiated list, here are practice questions grouped by the pattern they belong to, since practicing a few problems from the same family back to back is what actually builds recognition.

Include-or-exclude problems:

• Subsets
• Subsets II (handling duplicate numbers in the input)
• Combination Sum II (each number used at most once, input may contain duplicates)
• Partition Equal Subset Sum (as a backtracking warm-up before seeing its DP version)

Fixed-length arrangement problems:

• Permutations
• Permutations II (handling duplicate numbers in the input)
• Letter Case Permutation
• Next Permutation (a good problem for contrasting backtracking against a more direct approach)

Unlimited-reuse combination problems:

• Combination Sum
• Combination Sum III (fixed number of elements allowed, digits 1-9 only)
• Factor Combinations

Grid and graph exploration problems:

• Word Search
• Word Search II (multiple target words at once, often paired with a Trie)
• Number of Islands (a good bridge between backtracking and pure graph traversal)
• Rat in a Maze / Path finding in a grid with obstacles

String-splitting problems:

• Palindrome Partitioning
• Restore IP Addresses
• Word Break II (returning every valid way to break a string into dictionary words)

Constraint satisfaction / board problems:

• N-Queens
• N-Queens II (just the count, a good exercise in simplifying an existing solution)
• Sudoku Solver
• Generate Parentheses (balancing an "open" and "close" constraint at every step)

A genuinely useful way to practice, pick one problem from each category, solve it fully using the template from Section 4 and only then move to a second problem from the same category to confirm the pattern actually stuck, before moving to the next category entirely.

FAQ

1. Is backtracking the same as recursion?

Not exactly, backtracking is recursion with a specific discipline added to it. you undo a choice before trying the next one, so every branch explores from a clean state.

2. Why do we need to "unchoose" if the recursive call already finished?

Because the same variable (like a list, a grid or a "used" array) is shared across every branch of the exploration. If you don't undo your choice, the next branch starts with leftover state from a path that's already been abandoned.

3. How do I know when to stop exploring a branch early?

Ask yourself, "based on what I know right now, could this partial attempt possibly still succeed?" If the answer is clearly no, stop immediately instead of continuing deeper, that's pruning, covered in Section 11.

4. Is backtracking always slow?

It can be, in the worst case, since it's fundamentally still exploring many possibilities. Good pruning is what keeps it fast in practice on most real inputs, even though the theoretical worst case remains exponential.

5. What's the time complexity of a typical backtracking solution?

It varies a lot by problem, but it's often exponential in the size of the input, since you're exploring a tree of choices that branches at every step. Pruning reduces the practical running time significantly without changing this worst-case label.

6. Do I need a visited array in every backtracking problem?

No, only when a problem restricts reusing the same item or position within a single path, like Word Search or Permutations. Problems that explicitly allow reuse, like Combination Sum, don't need one.

7. How is backtracking different from BFS or DFS?

Backtracking is really DFS with the added discipline of undoing choices and pruning invalid branches early. Every backtracking solution is technically a DFS, but not every DFS needs the "unchoose" step, since plain graph traversal doesn't usually build up a shared, mutable partial solution the way backtracking problems do.

8. Why does my backtracking solution return duplicate results?

This usually happens when the input itself has duplicate values and your code doesn't explicitly skip over them, leading to the same combination being built through two different paths in the recursion tree.

9. Should I always use a start index in my for loop?

Only when the order of picking elements shouldn't matter, like in Subsets and Combination Sum, using a start index prevents you from generating the same combination in multiple different orders. Permutations, where order genuinely matters, intentionally loops from the beginning every time instead.

10. Can backtracking be converted into Dynamic Programming?

Sometimes, if the problem is only asking for a count or best value rather than every individual result and if it turns out the same exact subproblem is being solved repeatedly. If it's asking for every distinct valid arrangement, it usually has to stay as backtracking, since DP isn't built for enumerating every result individually.

11. What's the fastest way to get comfortable with backtracking?

Solve the six worked examples in this article by hand first, tracing through them on paper exactly like we did for Subsets and Combination Sum, before typing any code, seeing the recursion tree with your own eyes is what makes the "choose, explore, unchoose" rhythm feel natural instead of memorized.

Key Takeaways

• Backtracking is DFS with a specific rhythm: choose a option, explore where it leads, then undo it before trying the next option.
• The "unchoose" step is not optional bookkeeping : skipping it silently corrupts your results without any error being thrown.
• Every backtracking problem in this article shares the exact same skeleton from Section 4 : the differences are always in what counts as a valid choice and what counts as a finished solution.
• Pruning : stopping early on branches that clearly can't succeed, is what makes backtracking fast enough to actually use, not just theoretically correct.
• Recognizing the handful of recurring patterns (include/exclude, fixed arrangement, unlimited reuse, grid exploration, string splitting, constraint satisfaction) matters far more than memorizing individual problems.

Related Articles

Dynamic Programming for Beginners: Thinking in Subproblems

How to Approach Any DSA Interview Problem: A Complete Step-by-Step Guide

Sliding Window Pattern: When and How to Use It

What is Two Pointer Approach: When and How to Use It

Real Interview Experiences: Google, Amazon and Meta

The Ultimate DSA Practice Sheet for FAANG Interviews

Trending Developer Reads

Cursor vs Copilot : Which AI Coding Assistant Wins in 2025?

Meesho SDE-1 Online Assessment Interview Experience (Remote) - Rejected

System Design Deep Dive: 25 Essential Interview Questions

Zepto SDE-1 Interview Experience (Backend Developer) : Real DSA, LLD, Chess Game Design

Uber SDE 2 Interview Experience (5 Rounds, Selected) - Complete DSA Questions with solution, System Design & Managerial Round

JioHotstar Staff Software Engineer Interview Experience (Bangalore)

My Adobe SDE Interview Experience (Aug 2026) 5 Rounds, Selected

DSA Patterns for Coding Interviews: Complete LeetCode Roadmap (Beginner to Advanced)

Amazon SDE II Interview Experience (Bangalore, Selected) ~ Aug 2026

Blinkit (Eternal) SDE-1 Interview Experience (June 2026) – Offer Received

Responses (0)

Write a response

Hide Comments

No Comments yet.

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -34%

iQOO Amazon's Choice

iQOO Z10 Lite 5G — Cyber Green, 4GB RAM, 128GB Storage

Dimensity 6300 · 50MP Sony AI Camera · 6000 mAh · IP64

★★★★★★★★★★ 4.0 (2,052) 500+ bought last month

₹18,997 M.R.P. ₹28,999Save ₹10,002

Buy Now →

\n \n \n \n \n

The first time I saw a backtracking problem in an interview, I remember writing a solution that technically worked, but it took me nearly the whole 45 minutes and I couldn't explain why it worked. I had basically copied the shape of a solution I'd seen before and hoped the interviewer wouldn't ask me to explain it. He did. I fumbled.

Years later, sitting on the other side of the table, I see this exact same thing happen almost every week. Someone writes a backtracking solution that passes, but the moment I ask \"why did you undo that step after the recursive call,\" they go quiet. That line : the \"undo\" line, is the entire idea of backtracking and if you don't understand why it's there, you haven't actually learned backtracking, you've just memorized a shape.

This article is going to slow down on that exact point. Backtracking is not a scary, advanced topic. It's something you already do naturally, think about solving a maze with a pencil. you walk down a path and the moment you hit a dead end, you don't throw away the paper, you just erase your last few steps and try a different direction from the last place you had a choice. That's it. That's backtracking. Everything else in this article is just teaching you to do that \"erase and try again\" step in code, cleanly and reliably, on any problem.

What Backtracking Actually Is

Backtracking is a way of exploring every possible option for a problem, but doing it smartly. you build a solution one small decision at a time and the moment you realize a path can't possibly lead anywhere good, you step back and try a different decision instead of continuing down a path you already know is wrong.

Here's a real-life comparison that helps this click for most people. Imagine you're trying to find your way out of a real hedge maze. At every junction, you pick a direction and keep walking. If you hit a dead end, you don't teleport back to the entrance and start completely over. you just walk back to the last junction where you had another unexplored option and try that one instead. You keep doing this until you either find the exit or you've genuinely tried every path from every junction. That walking-back step is backtracking and the reason it's efficient compared to \"start completely over each time\" is that you're reusing all the walking you already did to reach that junction.

In code, this shows up as recursion with one small but important extra habit, after you try a choice and explore where it leads, you undo that choice before trying the next one so that every branch of your exploration starts from a clean, honest state, exactly like standing back at that junction with no memory of which direction you tried last.

Choose, Explore, Unchoose : The Core Idea

Nearly every backtracking solution, no matter how different the problems look on the surface, follows the same three-step rhythm:

\n
• Choose : pick one option out of the available choices at this step and add it to your current, in-progress solution.
\n
• Explore : recursively continue building the rest of the solution, now that this choice has been made.
\n
• Unchoose : remove that choice from your current solution before trying the next available option, so the next attempt starts fresh, unaffected by the choice you just tried.
\n

That third step, \"unchoose,\" is the one beginners forget most often and it's also the one that actually gives backtracking its name. you're literally tracking back to where you were before you made a choice, so you can try a different one. Skip it and your current, in-progress solution slowly turns into a mess that mixes leftover pieces from choices you already abandoned, which produces wrong answers in a way that's genuinely confusing to debug, because the code doesn't crash. it just quietly gives you garbage.

Let's make this concrete with something almost childishly simple: listing every possible outfit from 2 shirts and 2 pants.

\n
• Choose shirt A → choose pants X → we have outfit (A, X), record it → unchoose pants X
\n
• Choose pants Y → outfit (A, Y), record it → unchoose pants Y
\n
• Unchoose shirt A
\n
• Choose shirt B → choose pants X → outfit (B, X), record it → unchoose pants X
\n
• Choose pants Y → outfit (B, Y), record it → unchoose pants Y
\n
• Unchoose shirt B
\n

Notice how \"unchoose shirt A\" happens right before we move on to shirt B if we skipped it, shirt A would still be sitting in our current outfit when we tried to add shirt B and we'd end up with a broken combination. This tiny outfit example has no real complexity to it, but it contains 100% of the logic that powers every backtracking problem in this article, including the hard ones later on.

Backtracking vs Brute Force vs Dynamic Programming

These three get mixed up a lot, so let's separate them clearly, because knowing which one a problem actually needs saves you from forcing the wrong tool onto it.

Here's a genuinely useful way to remember the difference between backtracking and DP specifically, since these two get confused the most: DP is for questions like \"what's the best score,\" and backtracking is for questions like \"show me every valid way.\" If a problem asks you to generate all subsets, all permutations, all valid board arrangements or all paths that satisfy some rule that's backtracking's territory, not DP's, because DP is built around avoiding repeated identical subproblems and most backtracking problems don't actually revisit the exact same state twice in the first place.

The Universal Backtracking Template

Here is the shape I use for genuinely every backtracking problem I solve and it's worth memorizing this structure, not because memorizing is the goal, but because once this shape is second nature, your energy goes entirely into the problem-specific parts instead of the plumbing around them.

\nvoid backtrack(State currentState, Choices remainingChoices, Result result) {\n    if (isGoalReached(currentState)) {\n        recordSolution(currentState, result);\n        return; // or don't return, if you want to keep exploring further too\n    }\n\n    for (Choice choice : remainingChoices) {\n        if (!isValid(choice, currentState)) {\n            continue; // skip choices that break the problem's rules\n        }\n\n        makeChoice(choice, currentState);      // Choose\n        backtrack(currentState, updatedChoices, result); // Explore\n        undoChoice(choice, currentState);      // Unchoose\n    }\n}\n

Every single worked example in this article is this exact same skeleton, with the four blanks : isGoalReached, isValid, makeChoice, undoChoice : filled in differently depending on the problem. Once you see this pattern repeat across six genuinely different-looking problems, you'll stop seeing backtracking as \"a bunch of separate tricky problems\" and start seeing it as one idea wearing different outfits.

Worked Example 1 : Subsets

The problem: Given an array of distinct numbers, return every possible subset (including the empty set and the full set itself). Example: [1, 2, 3] should produce [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

The way to think about this, at every number in the array, you genuinely have a binary decision, include it in the current subset or don't. Backtracking explores this by walking through the array once and at each position, trying \"include\" and then, after exploring everything that follows, trying \"don't include.\"

\nimport java.util.*;\npublic class Subsets {\n    public static List<List<Integer>> subsets(int[] nums) {\n        List<List<Integer>> result = new ArrayList<>();\n        backtrack(nums, 0, new ArrayList<>(), result);\n        return result;\n    }\n    private static void backtrack(int[] nums, int start, List<Integer> current,\n                                    List<List<Integer>> result) {\n        // every state we reach, even a partial one, is itself a valid subset\n        result.add(new ArrayList<>(current));\n        for (int i = start; i < nums.length; i++) {\n            current.add(nums[i]);                 // Choose\n            backtrack(nums, i + 1, current, result); // Explore\n            current.remove(current.size() - 1);    // Unchoose\n        }\n    }\n}\n

Notice something a bit different here compared to the outfit example : we record the answer at every call, not just at the \"end\" of the recursion, because in this particular problem, every partial combination we build along the way is itself a valid, complete subset. This is a small but important detail: where exactly you record your answer depends entirely on what counts as a \"finished\" solution for that specific problem and it's the first thing to figure out before writing any code.

A quick trace on [1, 2]: start with current = [], record []. Then choose 1 → current = [1], record [1]. Then choose 2 → current = [1, 2], record [1, 2]. Unchoose 2 → back to [1]. Unchoose 1 → back to []. Then choose 2 → current = [2], record [2]. Unchoose 2 → back to [], loop ends. Final results: [], [1], [1,2], [2] : all four subsets of a 2-element array, exactly as expected.

Worked Example 2 : Permutations

The problem: given an array of distinct numbers, return every possible ordering (permutation) of them. Example: [1, 2, 3] should produce all 6 orderings, like [1,2,3], [1,3,2], [2,1,3] and so on.

This is a genuinely different flavor from subsets here, order matters and every element must be used exactly once in every result. The key extra piece of bookkeeping is a way to know which elements have already been used in the current arrangement, so you don't accidentally reuse one.

import java.util.*;\n\npublic class Permutations {\n    public static List<List<Integer>> permute(int[] nums) {\n        List<List<Integer>> result = new ArrayList<>();\n        boolean[] used = new boolean[nums.length];\n        backtrack(nums, new ArrayList<>(), used, result);\n        return result;\n    }\n\n    private static void backtrack(int[] nums, List<Integer> current, boolean[] used,\n                                    List<List<Integer>> result) {\n        if (current.size() == nums.length) {\n            result.add(new ArrayList<>(current)); // a full-length arrangement is our goal\n            return;\n        }\n        for (int i = 0; i < nums.length; i++) {\n            if (used[i]) continue; // skip anything already placed in this arrangement\n\n            used[i] = true;\n            current.add(nums[i]);                       // Choose\n            backtrack(nums, current, used, result);      // Explore\n            current.remove(current.size() - 1);          // Unchoose\n            used[i] = false;\n        }\n    }\n}\n

The used array is doing exactly the same job as the visited grid we'll see later in Word Search. it's how backtracking keeps track of \"what's already part of my current path,\" so it never reuses something it shouldn't. This is a pattern worth remembering on its own: whenever a problem says \"each item can only be used once,\" you almost always need some kind of used or visited tracker sitting right next to your recursion.

Worked Example 3 : Combination Sum

The problem: given a set of distinct candidate numbers and a target, find every unique combination of candidates that sums exactly to the target. The same number can be reused as many times as needed. Example: candidates = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]].

This one introduces a genuinely useful new idea, since numbers can repeat, when you \"choose\" a candidate, you allow the very next recursive call to choose that same candidate again but to avoid producing the same combination in a different order (like both [2,2,3] and [2,3,2]), you only ever look forward from your current position, never backward.

import java.util.*;\n\npublic class CombinationSum {\n    public static List<List<Integer>> combinationSum(int[] candidates, int target) {\n        List<List<Integer>> result = new ArrayList<>();\n        backtrack(candidates, target, 0, new ArrayList<>(), result);\n        return result;\n    }\n\n    private static void backtrack(int[] candidates, int remaining, int start,\n                                    List<Integer> current, List<List<Integer>> result) {\n        if (remaining == 0) {\n            result.add(new ArrayList<>(current)); // hit the target exactly\n            return;\n        }\n        if (remaining < 0) {\n            return; // overshot the target, this path is dead\n        }\n        for (int i = start; i < candidates.length; i++) {\n            current.add(candidates[i]);\n            // pass 'i', not 'i + 1' : this candidate can be reused again\n            backtrack(candidates, remaining - candidates[i], i, current, result);\n            current.remove(current.size() - 1);\n        }\n    }\n}\n

That single difference : passing i instead of i + 1 into the recursive call, is the entire trick that allows reuse and it's worth comparing directly against the Permutations example, where every choice moves strictly forward with no repeats allowed. Small details like this one are exactly what separates \"understanding backtracking\" from \"having memorized one specific backtracking solution\", the skeleton is identical, but this one line changes the entire behavior of the algorithm.

Tracing candidates = [2, 3, 6, 7], target = 7: choosing 2, 2, 2 overshoots to remaining = 1, then every further candidate overshoots further, so that branch dies without a result. Backing up to 2, 2, 3 gives remaining = 0 exactly : recorded. Backing up further and trying 2, 3 then 3 again overshoots. Eventually the branch starting fresh with 7 alone also hits remaining = 0 recorded. Final result: [[2, 2, 3], [7]], matching the expected output exactly.

Worked Example 4 : Word Search

The problem: given a 2D grid of letters and a target word, determine if the word can be formed by moving to adjacent cells (up, down, left, right), without reusing the same cell twice within one word.

This example moves backtracking from \"building a list\" to \"exploring a grid,\" which is an extremely common real-world shape, think of how a game character explores a map or how a maze-solving robot decides which direction to try next.

public class WordSearch {\n    public static boolean exist(char[][] board, String word) {\n        int rows = board.length;\n        int cols = board[0].length;\n        boolean[][] visited = new boolean[rows][cols];\n\n        for (int r = 0; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                if (backtrack(board, word, 0, r, c, visited)) {\n                    return true; // found a valid starting point that works\n                }\n            }\n        }\n        return false;\n    }\n\n    private static boolean backtrack(char[][] board, String word, int index,\n                                       int row, int col, boolean[][] visited) {\n        if (index == word.length()) {\n            return true; // matched every character of the word\n        }\n        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {\n            return false; // walked off the grid\n        }\n        if (visited[row][col] || board[row][col] != word.charAt(index)) {\n            return false; // already used or letter doesn't match\n        }\n\n        visited[row][col] = true; // Choose\n\n        // Explore all four directions\n        boolean found = backtrack(board, word, index + 1, row + 1, col, visited)\n                      || backtrack(board, word, index + 1, row - 1, col, visited)\n                      || backtrack(board, word, index + 1, row, col + 1, visited)\n                      || backtrack(board, word, index + 1, row, col - 1, visited);\n\n        visited[row][col] = false; // Unchoose : this cell might work for a different path later\n        return found;\n    }\n}\n

The visited grid is undone (visited[row][col] = false) right before returning, regardless of whether this particular path found the word or not. This matters because a cell that didn't work as part of this attempted path might still work perfectly fine as part of a different path starting somewhere else on the grid and if you forgot to unmark it, you'd wrongly treat that cell as permanently unusable for the rest of the search.

Worked Example 5 : Palindrome Partitioning

The problem: given a string, split it into pieces such that every single piece is a palindrome and return every possible way to do this. Example: \"aab\" → [[\"a\",\"a\",\"b\"], [\"aa\",\"b\"]].

This example introduces a new kind of choice, instead of picking one item from a list, you're picking where to cut the string next.

import java.util.*;\n\npublic class PalindromePartitioning {\n    public static List<List<String>> partition(String s) {\n        List<List<String>> result = new ArrayList<>();\n        backtrack(s, 0, new ArrayList<>(), result);\n        return result;\n    }\n\n    private static void backtrack(String s, int start, List<String> current,\n                                    List<List<String>> result) {\n        if (start == s.length()) {\n            result.add(new ArrayList<>(current)); // used up the whole string\n            return;\n        }\n\n        for (int end = start + 1; end <= s.length(); end++) {\n            String piece = s.substring(start, end);\n            if (isPalindrome(piece)) {\n                current.add(piece);                        // Choose this cut\n                backtrack(s, end, current, result);         // Explore from here\n                current.remove(current.size() - 1);          // Unchoose\n            }\n            // if it's not a palindrome, we simply skip it : no need to explore further\n        }\n    }\n\n    private static boolean isPalindrome(String s) {\n        int left = 0, right = s.length() - 1;\n        while (left < right) {\n            if (s.charAt(left) != s.charAt(right)) return false;\n            left++;\n            right--;\n        }\n        return true;\n    }\n}\n

Notice the if (isPalindrome(piece)) check sitting right before we choose to explore that cut. this is our first real look at pruning, which is worth its own dedicated section next, because it's the single biggest reason backtracking is usable at all on anything beyond tiny inputs.

Worked Example 6 : N-Queens

The problem: place n queens on an n x n chessboard so that no two queens attack each other, meaning no two queens share a row, a column or a diagonal. Count (or list) all valid arrangements.

This is the example I use to show people that backtracking scales up to genuinely hard-looking problems using the exact same skeleton as the outfit example from Section 2 : nothing new conceptually, just more careful bookkeeping about what counts as \"valid.\"

Since we place one queen per row, we only ever need to decide which column each row's queen goes in, which already eliminates the \"same row\" conflict for free. We track used columns and used diagonals directly, so checking validity is fast.

public class NQueens {\n    public static int totalNQueens(int n) {\n        boolean[] usedCols = new boolean[n];\n        boolean[] usedDiag1 = new boolean[2 * n]; // identified by (row + col)\n        boolean[] usedDiag2 = new boolean[2 * n]; // identified by (row - col + n)\n        return backtrack(0, n, usedCols, usedDiag1, usedDiag2);\n    }\n\n    private static int backtrack(int row, int n, boolean[] usedCols,\n                                   boolean[] usedDiag1, boolean[] usedDiag2) {\n        if (row == n) {\n            return 1; // successfully placed a queen in every row : one valid arrangement\n        }\n\n        int count = 0;\n        for (int col = 0; col < n; col++) {\n            int diag1 = row + col;\n            int diag2 = row - col + n;\n\n            if (usedCols[col] || usedDiag1[diag1] || usedDiag2[diag2]) {\n                continue; // this column or diagonal is already under attack, skip it\n            }\n\n            usedCols[col] = usedDiag1[diag1] = usedDiag2[diag2] = true;   // Choose\n            count += backtrack(row + 1, n, usedCols, usedDiag1, usedDiag2); // Explore\n            usedCols[col] = usedDiag1[diag1] = usedDiag2[diag2] = false;  // Unchoose\n\n        }\n        return count;\n    }\n}\n

For n = 4, this correctly returns 2, matching the two well-known valid arrangements for a 4x4 board. The diagonal tracking is the only genuinely new idea here, every cell along the same \"downward-right\" diagonal shares the same value of row - col and every cell along the same \"downward-left\" diagonal shares the same value of row + col. That's a small piece of math worth sitting with on paper for a minute, but once it clicks, it unlocks a whole family of grid and board-based backtracking problems.

Pruning : Cutting Off Bad Branches Early

Pruning is what separates a backtracking solution that finishes in a fraction of a second from one that technically works but takes forever on anything but the tiniest input. The idea is simple: the moment you can tell a partial solution has no chance of leading anywhere valid, stop exploring it immediately, instead of continuing on and discovering the failure later.

You've actually already seen pruning multiple times in this article, without me naming it yet:

\n
• In Combination Sum, the line if (remaining < 0) return; prunes away any path the instant it overshoots the target. there's no reason to keep adding more numbers to a sum that's already too big.
\n
• In Palindrome Partitioning, only exploring further when isPalindrome(piece) is true prunes away every cut that couldn't possibly lead to a valid full partition.
\n
• In N-Queens, checking usedCols, usedDiag1 and usedDiag2 before placing a queen prunes away placements that are already guaranteed to conflict, rather than placing the queen and discovering the conflict several rows later.
\n

The general lesson: look for a check you can perform right now, before going deeper, that would let you skip an entire branch of possibilities in one move. Every real pruning check follows this same shape \"is there any way this partial attempt could possibly succeed? If clearly not, stop right here.\" Getting good at spotting these checks is genuinely most of what separates a slow backtracking solution from a fast one, far more than any clever data structure.

Common Patterns You'll See Again and Again

Once you've solved enough backtracking problems, you start noticing they cluster into a small number of recurring shapes. Here they are, described by their thought process rather than their names, since recognizing the shape matters more than the label:

\n
• Include-or-exclude problems (like Subsets) : at every element, you have exactly two choices: take it or skip it. The decision tree naturally branches into two at every step.
\n
• Fixed-length arrangement problems (like Permutations) : every element must be used exactly once, order matters and you need a used tracker to avoid repeats.
\n
• Unlimited-reuse combination problems (like Combination Sum) : elements can be reused, so your recursive call moves forward from the current position rather than the next one.
\n
• Grid or graph exploration problems (like Word Search) : you move between neighboring positions, need a visited tracker for the current path and often explore in multiple directions from each cell.
\n
• String-splitting problems (like Palindrome Partitioning) : instead of choosing from a fixed list, you're choosing where to make the next cut in a string.
\n
• Constraint satisfaction / board problems (like N-Queens and Sudoku solvers built the same way) : you place items one at a time onto a structure while tracking several overlapping rules (rows, columns, diagonals, boxes), pruning aggressively whenever a rule would be broken.
\n

If a new problem doesn't cleanly match one of these, don't panic, most real backtracking problems are actually a small combination of two of these shapes stitched together, like a grid-exploration problem that also involves a used-once constraint or a combination problem with an extra include/exclude rule layered on top.

How to Spot a Backtracking Problem

The honest signals I look for, the same ones worth training yourself to notice:

\n
• The question asks for all possible results : all subsets, all permutations, all valid arrangements, all paths, not just a single best number.
\n
• The question asks whether at least one valid arrangement exists and satisfying it requires trying different combinations of choices, like Word Search or Sudoku.
\n
• Choices made earlier in the problem genuinely restrict what choices are available later, placing a queen affects which columns remain safe, using a letter in a grid affects which cells are still available.
\n
• Brute-force \"try everything\" would technically work but is clearly wasteful, because many partial attempts can be abandoned early once you notice they've already broken a rule.
\n

If a question instead asks for a single maximum, minimum or count derived from overlapping smaller versions of the exact same subproblem, that's more likely pointing you toward Dynamic Programming, as covered in the previous article in this series : it's genuinely worth reading both, because the overlap and contrast between the two topics helps both of them stick better in your memory.

Common Mistakes Beginners Make

\n
• Forgetting the \"unchoose\" step, which quietly corrupts your current state across different branches and produces confusing, wrong output without ever throwing an error.
\n
• Copying a list by reference instead of creating a new copy when recording a result : writing result.add(current) instead of result.add(new ArrayList<>(current)). Since current keeps changing as the recursion continues, every entry you added earlier ends up pointing to the same, now-different list and your final results all end up looking wrong or identical.
\n
• Not pruning early enough, which technically still produces the correct answer but can make an otherwise reasonable solution painfully slow on larger inputs.
\n
• Confusing \"used\" tracking between problems that allow reuse and problems that don't : using i + 1 when a problem actually allows reuse or using i when it doesn't, silently changes the entire meaning of your solution.
\n
• Not clearly defining what counts as a \"complete\" solution before coding. In Subsets, every partial state is already complete. In Permutations, only a full-length arrangement counts. Mixing these up leads to either missing results or way too many incorrect ones.
\n
• Trying to solve grid problems without a visited tracker, which usually causes infinite loops as the recursion walks back and forth between the same two cells forever.
\n

Practice Questions by Pattern

Rather than one long undifferentiated list, here are practice questions grouped by the pattern they belong to, since practicing a few problems from the same family back to back is what actually builds recognition.

Include-or-exclude problems:

\n
• Subsets
\n
• Subsets II (handling duplicate numbers in the input)
\n
• Combination Sum II (each number used at most once, input may contain duplicates)
\n
• Partition Equal Subset Sum (as a backtracking warm-up before seeing its DP version)
\n

Fixed-length arrangement problems:

\n
• Permutations
\n
• Permutations II (handling duplicate numbers in the input)
\n
• Letter Case Permutation
\n
• Next Permutation (a good problem for contrasting backtracking against a more direct approach)
\n

Unlimited-reuse combination problems:

\n
• Combination Sum
\n
• Combination Sum III (fixed number of elements allowed, digits 1-9 only)
\n
• Factor Combinations
\n

Grid and graph exploration problems:

\n
• Word Search
\n
• Word Search II (multiple target words at once, often paired with a Trie)
\n
• Number of Islands (a good bridge between backtracking and pure graph traversal)
\n
• Rat in a Maze / Path finding in a grid with obstacles
\n

String-splitting problems:

\n
• Palindrome Partitioning
\n
• Restore IP Addresses
\n
• Word Break II (returning every valid way to break a string into dictionary words)
\n

Constraint satisfaction / board problems:

\n
• N-Queens
\n
• N-Queens II (just the count, a good exercise in simplifying an existing solution)
\n
• Sudoku Solver
\n
• Generate Parentheses (balancing an \"open\" and \"close\" constraint at every step)
\n

A genuinely useful way to practice, pick one problem from each category, solve it fully using the template from Section 4 and only then move to a second problem from the same category to confirm the pattern actually stuck, before moving to the next category entirely.

FAQ

1. Is backtracking the same as recursion?

Not exactly, backtracking is recursion with a specific discipline added to it. you undo a choice before trying the next one, so every branch explores from a clean state.

2. Why do we need to \"unchoose\" if the recursive call already finished?

Because the same variable (like a list, a grid or a \"used\" array) is shared across every branch of the exploration. If you don't undo your choice, the next branch starts with leftover state from a path that's already been abandoned.

3. How do I know when to stop exploring a branch early?

Ask yourself, \"based on what I know right now, could this partial attempt possibly still succeed?\" If the answer is clearly no, stop immediately instead of continuing deeper, that's pruning, covered in Section 11.

4. Is backtracking always slow?

It can be, in the worst case, since it's fundamentally still exploring many possibilities. Good pruning is what keeps it fast in practice on most real inputs, even though the theoretical worst case remains exponential.

5. What's the time complexity of a typical backtracking solution?

It varies a lot by problem, but it's often exponential in the size of the input, since you're exploring a tree of choices that branches at every step. Pruning reduces the practical running time significantly without changing this worst-case label.

6. Do I need a visited array in every backtracking problem?

No, only when a problem restricts reusing the same item or position within a single path, like Word Search or Permutations. Problems that explicitly allow reuse, like Combination Sum, don't need one.

7. How is backtracking different from BFS or DFS?

Backtracking is really DFS with the added discipline of undoing choices and pruning invalid branches early. Every backtracking solution is technically a DFS, but not every DFS needs the \"unchoose\" step, since plain graph traversal doesn't usually build up a shared, mutable partial solution the way backtracking problems do.

8. Why does my backtracking solution return duplicate results?

This usually happens when the input itself has duplicate values and your code doesn't explicitly skip over them, leading to the same combination being built through two different paths in the recursion tree.

9. Should I always use a start index in my for loop?

Only when the order of picking elements shouldn't matter, like in Subsets and Combination Sum, using a start index prevents you from generating the same combination in multiple different orders. Permutations, where order genuinely matters, intentionally loops from the beginning every time instead.

10. Can backtracking be converted into Dynamic Programming?

Sometimes, if the problem is only asking for a count or best value rather than every individual result and if it turns out the same exact subproblem is being solved repeatedly. If it's asking for every distinct valid arrangement, it usually has to stay as backtracking, since DP isn't built for enumerating every result individually.

11. What's the fastest way to get comfortable with backtracking?

Solve the six worked examples in this article by hand first, tracing through them on paper exactly like we did for Subsets and Combination Sum, before typing any code, seeing the recursion tree with your own eyes is what makes the \"choose, explore, unchoose\" rhythm feel natural instead of memorized.

Key Takeaways

\n
• Backtracking is DFS with a specific rhythm: choose a option, explore where it leads, then undo it before trying the next option.
\n
• The \"unchoose\" step is not optional bookkeeping : skipping it silently corrupts your results without any error being thrown.
\n
• Every backtracking problem in this article shares the exact same skeleton from Section 4 : the differences are always in what counts as a valid choice and what counts as a finished solution.
\n
• Pruning : stopping early on branches that clearly can't succeed, is what makes backtracking fast enough to actually use, not just theoretically correct.
\n
• Recognizing the handful of recurring patterns (include/exclude, fixed arrangement, unlimited reuse, grid exploration, string splitting, constraint satisfaction) matters far more than memorizing individual problems.
\n

Related Articles