Blog 8: Decision Tree Pattern in Backtracking 🌳

At its heart, backtracking explores a decision tree:

• Each level of the tree = a decision to make.
• Each branch = one possible choice.
• Each leaf = a solution or a dead end.

This perspective makes backtracking problems easier to visualize and structure.

---

🔹 Why Decision Tree View Matters?

• Helps you model recursive choices clearly.
• Useful for generating combinations, permutations, subsets, partitions, and expressions.
• Many problems can be solved by simply walking the decision tree systematically.

---

🔹 Problem 1: Subsets (LeetCode 78)

Generate all subsets of a given set.

Decision Tree for [1,2,3]

             []
       /             \
     [1]             []
    /   \           /   \
 [1,2]  [1]      [2]    []
   / \    / \     / \    / \
123 12  13  1   23  2   3   []

Each level = whether to include/exclude an element.

---

Java Code

import java.util.*;

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, nums, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int index, int[] nums, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path)); // every node in tree is a subset

        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);              // choose
            backtrack(i + 1, nums, path, result); // explore
            path.remove(path.size() - 1);   // unchoose (backtrack)
        }
    }
}

---

🔹 Problem 2: Permutations (LeetCode 46)

Generate all permutations of given array.

Decision tree: at each step, choose one unused element.

Java Code

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

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

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

---

🔹 Problem 3: Generate Parentheses (LeetCode 22)

Generate all valid parentheses strings of length 2n.

Decision tree: at each step, decide add "(" or ")" (with constraints).

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) {
            result.add(sb.toString());
            return;
        }

        if (open < n) {
            sb.append("(");
            backtrack(result, sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);
        }

        if (close < open) {
            sb.append(")");
            backtrack(result, sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

🔹 Problem 4: Expression Add Operators (LeetCode 282)

Insert +, -, * between digits to reach a target.

Decision tree: at each position, decide which operator to insert (or none).

---

🔹 Variations of Decision Tree Problems

1. Combinations (LeetCode 77) – choose k elements.
2. Combination Sum (LeetCode 39, 40) – sum up to target with/without duplicates.
3. Palindrome Partitioning (LeetCode 131) – break string into palindrome substrings.
4. Word Break (LeetCode 140) – break string into valid dictionary words.
5. IP Address Restoration (LeetCode 93) – split string into 4 valid segments.

---

🔹 Key Takeaways

✅ Think of backtracking as walking a decision tree.
✅ Each recursive call = one level in the tree.
✅ Subsets = binary tree (choose/exclude).
✅ Permutations = factorial tree (choose unused element).
✅ Parentheses/expressions = constrained decision trees.

---