Java.Algo.2ApproachesForBacktracking

Let’s clearly compare and describe the two major approaches in backtracking:
👉 DFS Binary-style (Include/Exclude) and
👉 Loop-style (Iterative Recursive)

---

🧭 1. DFS Binary-style Backtracking

Also called: Include/Exclude recursion
This approach uses binary decision-making for each element:

“Do I include this item or not?”

---

🔹 Concept:

• At each index, you decide between two paths:
  • Include the element
  • Exclude the element

This forms a binary tree of decisions.

---

🔹 Code Template:

void backtrack(int index, int[] nums, List<Integer> path, List<List<Integer>> res) {
    if (index == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }

    // Exclude current
    backtrack(index + 1, nums, path, res);

    // Include current
    path.add(nums[index]);
    backtrack(index + 1, nums, path, res);
    path.remove(path.size() - 1); // backtrack
}

🔹 Use Cases:

• Subsets (2^n combinations of present/absent)
• Boolean decision trees
• Problems where each element must be included or excluded

---

🔹 Visual for [1, 2]:

            []
         /     \
       []       [1]
      /  \     /   \
    []  [2]  [1]  [1,2]

🧭 2. Loop-style Backtracking

Also called: For-loop DFS / Iterative recursion inside backtrack

This style uses a for loop inside the recursion to explore multiple candidates at each level.

---

🔹 Concept:

• Loop through all possible next elements
• Add one to the path, explore deeper
• Then backtrack (remove last)

---

🔹 Code Template:

void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));

    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // optional: skip duplicates
        path.add(nums[i]);
        backtrack(i + 1, nums, path, res);
        path.remove(path.size() - 1); // backtrack
    }
}

🔹 Use Cases:

• Combinations
• Subsets with unique combinations
• Permutations (with extra visited[] check)
• Sudoku, N-Queens, word search

---

🔹 Visual for [1, 2]:

Start at index 0
→ [1] → [1, 2]
→ [2]

generates

[], [1], [1,2], [2]

📊 Summary Table

Feature	Binary-style	Loop-style
Decision model	Include / Exclude (2 branches)	Pick one of many (loop)
Best for	Subsets, boolean combinations	Combinations, permutations
Handles duplicates easily	Needs extra logic or sorted input	Can skip duplicates in loop
Recursion depth	Always n	Varies depending on loop range
Structure	Binary tree	DFS with branching via loop

---

💡 Rule of Thumb:

| If each item is a yes/no decision → use binary-style.
| If you’re choosing next elements from a range → use loop-style. |