Backtracking : Master it like a pro

Core Idea:

"I do, I fail, I go back and try something else." - Nishchya Verma

Let's break it down:
"I do"
→ You make a choice or decision (e.g. placing a queen on a chessboard, choosing a number in Sudoku, picking a path in a maze).

"I fail"
→ You reach an invalid state — maybe a constraint is violated or no further progress is possible.

"I go back"
→ You undo the last decision — this is the "backtrack" part.

"Try something else"
→ Explore a different path by making another valid choice and continuing.

Backtracking = Try > Fail > Undo > Try Something Else

Think of it like a smart brute force approach where you:

1. Choose - Pick an option from a set.
2. Explore - Go deeper with that option.
3. Unchoose (Backtrack) - If it doesn’t lead to a solution, undo and try the next.

It’s used when:

• You need all possible combinations/permutations/subsets.
• You make decisions step by step, and some decisions may lead to dead ends.

How To Recognize a Backtracking Problem:

• "Find all..."
• "Count the number of ways..."
• "Return possible arrangements..."
• You’re asked to explore all combinations, permutations, paths, or valid configurations.
• Constraints must be obeyed (e.g. Sudoku, N-Queens).

Template

function backtrack(path, options) {
    if (isGoal(path)) {
        result.push([...path]); // or return true if only one solution is needed
        return;
    }

    for (let option of options) {
        if (isValid(option, path)) {
            path.push(option);             // Choose
            backtrack(path, updatedOptions); // Explore
            path.pop();                   // Unchoose (Backtrack)
        }
    }
}

Let’s Learn by Examples

Let’s dive into two famous problems where backtracking is not just helpful — it’s essential for solving them.

We’ll start with an easier problem to build confidence, then move on to a slightly more challenging one.

1. Permutations [Leetcode #43]

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

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:
Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Lets try to address it,

What are we doing here?
You're trying every possible arrangement of the numbers.
This is a backtracking problem:

    "Try, fail, go back, try something else."

Lets understand it visually for example
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Each level:

1. Chooses a number not already used
2. Adds it to the current path
3. Backtracks when needed (removes the last added number)

Lets write the backtrack code for above actions
Python

def permute(nums):
    result = []

    def backtrack(path):
        if len(path) == len(nums):       # base case: full permutation
            result.append(path[:])       # make a copy of path
            return

        for num in nums:
            if num in path:              # skip already used numbers
                continue
            path.append(num)             # make a choice
            backtrack(path)              # explore
            path.pop()                   # undo choice (backtrack)

    backtrack([])
    return result

Java

class Solution {
    List<List<Integer>> permutations = new ArrayList<>();
    int[] used;
    private void backtrack(int[] nums, ArrayList<Integer> temp) {
        if(temp.size() == nums.length) {
            permutations.add(new ArrayList<>(temp));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if(used[i] != 1) {
                temp.add(nums[i]);
                used[i] = 1;
                backtrack(nums, temp);
                used[i] = 0;
                temp.remove(temp.size()-1);
            }  
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        used = new int[nums.length];
        backtrack(nums, new ArrayList<Integer>());
        return permutations;
    }
}

Lets understand what is happening

• Start: []

• Choose 1 → [1]

  • Choose 2 → [1, 2]
    • Choose 3 → [1, 2, 3] ✅
    • Backtrack → [1, 2]
  • Backtrack → [1]
  • Choose 3 → [1, 3]
    • Choose 2 → [1, 3, 2] ✅
    • Backtrack → [1, 3]
  • Backtrack → [1]

• Backtrack → []

• Choose 2 → [2]

  • Choose 1 → [2, 1]
    • Choose 3 → [2, 1, 3] ✅
    • Backtrack → [2, 1]
  • Backtrack → [2]
  • Choose 3 → [2, 3]
    • Choose 1 → [2, 3, 1] ✅
    • Backtrack → [2, 3]
  • Backtrack → [2]

• Backtrack → []

• Choose 3 → [3]

  • Choose 1 → [3, 1]
    • Choose 2 → [3, 1, 2] ✅
    • Backtrack → [3, 1]
  • Backtrack → [3]
  • Choose 2 → [3, 2]
    • Choose 1 → [3, 2, 1] ✅
    • Backtrack → [3, 2]
  • Backtrack → [3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Lets take another example, a little complex this time.

2. Combinations [Leetcode #77]

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

You may return the answer in any order.

Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2:
Input: n = 1, k = 1
Output: [[1]]

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

Note - This is combinatorics, not permutations → Order doesn’t matter.
So [1, 2] and [2, 1] are same combination (we only want one of them).

Lets understand it visually for example
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

We start with an empty list, and at each level:

• Pick the next number from start to n
• Recurse deeper with one more number in the path
• Stop when path size reaches k

Lets write the backtrack code for above actions
Python

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:           # base case
            result.append(path[:])
            return

        for i in range(start, n + 1):
            path.append(i)           # make a choice
            backtrack(i + 1, path)   # explore next numbers
            path.pop()               # undo choice (backtrack)

    backtrack(1, [])
    return result

Java

class Solution {
    List<List<Integer>> solution;
    int size;
    private void backtrack(int n, int k, List<Integer> subset) {
        if(subset.size() == k) {
            solution.add(new ArrayList<>(subset));
            return;
        }
        for(int i = n;i<=size;i++) {
            subset.add(i);
            backtrack(i+1, k, subset);
            subset.remove(subset.size()-1);
        }

    }
    public List<List<Integer>> combine(int n, int k) {
        solution = new ArrayList<>();
        size = n;
        backtrack(1,k, new ArrayList<Integer>());
        return solution;
    }
}

Lets understand what is happening
Here, n=4 and k=2

• [] → [1] → [1,2] ✅
• Backtrack → [1] → [1,3] ✅
• Backtrack → [1,4] ✅
• Backtrack to [] → Try [2] → [2,3] ✅, [2,4] ✅
• Try [3] → [3,4] ✅

Total: 6 combinations

I’ll be sharing two carefully chosen problems to help you master this concept.
Once you've solved them, share your experience and solutions in the comments — let’s learn together!

Practice Questions

1. Generate Parentheses [Leetcode #22]

2. N-Queens [Leetcode #51]