# How the Backtracking Template Handles Pruning for Improved Efficiency in LeetCode

> Learn how the backtracking template in youngyangyang04/leetcode-master uses pruning in termination conditions and loop bounds to eliminate impossible branches, drastically improving efficiency.

- Repository: [程序员Carl/leetcode-master](https://github.com/youngyangyang04/leetcode-master)
- Tags: tutorial
- Published: 2026-03-05

---

**The backtracking template in the `youngyangyang04/leetcode-master` repository embeds pruning directly into the termination condition and for-loop bounds to eliminate impossible branches before they are explored, reducing time complexity from exponential to near-polynomial in practice.**

The `youngyangyang04/leetcode-master` repository provides a canonical backtracking template that demonstrates how to systematically cut off fruitless search paths. By integrating **pruning**—the strategic elimination of invalid branches—into the standard recursive skeleton, the template transforms a naïve exhaustive search into an efficient algorithm suitable for solving LeetCode combination and permutation problems.

## Where Pruning Fits in the Backtracking Template

The repository defines the standard backtracking workflow in `problems/算法模板.md`. This template consists of three sequential phases: termination checking, child-node iteration, and state restoration. Pruning hooks are inserted at the first two phases to prevent unnecessary recursion.

### The Termination Check as a Pruning Hook

The first line of defense is the **termination condition** (`if (终止条件)`). In addition to identifying valid solutions, this block detects impossible states—such as a partial sum exceeding the target—and returns immediately.

```cpp
void backtracking(参数) {
    // ① Termination + early prune
    if (sum > target) return;  // Prune: sum already too large
    if (path.size() == k) {
        if (sum == target) collectResult();
        return;
    }
    // ...
}

```

This pattern appears in `problems/0216.组合总和III.md`, where the `if (sum > targetSum) return;` statement prevents the algorithm from exploring supersets that can never satisfy the constraint.

### The For-Loop as a Branching Control Point

The second pruning opportunity lies within the **for-loop** that iterates over candidate elements. By constraining the iteration range based on remaining requirements, the template avoids spawning subtrees that lack sufficient elements to complete the solution.

```cpp
for (int i = startIndex; i <= n - (k - path.size()) + 1; ++i) {
    // Only iterate while enough numbers remain to fill the path
}

```

This **loop-range reduction** is documented in `problems/0077.组合优化.md`. The expression `n - (k - path.size()) + 1` calculates the last valid starting position where the remaining slots (`k - path.size()`) can still be filled with the numbers left (`n - i + 1`).

## Three Concrete Pruning Strategies in the Repository

The `leetcode-master` repository demonstrates three distinct pruning techniques that target different constraint types: cardinality constraints, numeric bounds, and state validity.

### Loop-Range Reduction for Combination Problems

When solving the "Combinations" problem (LeetCode 77), the repository applies pruning to enforce the cardinality constraint (selecting exactly `k` elements). Instead of iterating to `n`, the loop stops at `n - (k - path.size()) + 1`.

**Why this works:** If the current path contains `path.size()` elements, we need `k - path.size()` more. If the starting index `i` is greater than `n - (k - path.size()) + 1`, even selecting all remaining elements would yield fewer than `k` total items.

```cpp
// From problems/0077.组合优化.md
void backtracking(int n, int k, int startIndex) {
    if (path.size() == k) {
        result.push_back(path);
        return;
    }
    for (int i = startIndex; i <= n - (k - path.size()) + 1; ++i) {
        path.push_back(i);
        backtracking(n, k, i + 1);
        path.pop_back();
    }
}

```

### Sum-Based Pruning for Constrained Sums

For problems involving target sums (e.g., Combination Sum III, LeetCode 216), the repository introduces **sum-based pruning**. Before entering the for-loop or at the start of the recursive function, the algorithm checks if the accumulated sum already exceeds the target.

**Why this works:** All numbers in these problems are positive integers. Once `sum > target`, any further addition will only increase the gap, making it impossible to reach the target. The branch is therefore abandoned immediately.

```cpp
// From problems/0216.组合总和III.md
void backtracking(int targetSum, int k, int sum, int startIndex) {
    if (sum > targetSum) return;  // Prune: sum already exceeded
    
    if (path.size() == k) {
        if (sum == targetSum) result.push_back(path);
        return;
    }
    
    // Loop-range prune also applied here
    for (int i = startIndex; i <= 9 - (k - path.size()) + 1; ++i) {
        sum += i;
        path.push_back(i);
        backtracking(targetSum, k, sum, i + 1);
        sum -= i;
        path.pop_back();
    }
}

```

### Early Exit on Invalid States

Beyond numeric constraints, the template supports **state-based pruning** for problems with complex validity rules (e.g., N-Queens, Sudoku). In these cases, a helper function checks if the current partial state violates any constraints before recursing.

While not explicitly detailed in the provided analysis files, the pattern follows the same structure: an immediate `return` if `state.invalid()` is true, placed immediately after the termination check.

## Complete Code Examples

The following snippets demonstrate the pruning techniques as implemented in the repository. Each example is self-contained and runnable in a C++ environment.

### Example 1: Combination with Loop-Range Pruning

This implementation of LeetCode 77 demonstrates how to reduce the search space by constraining the for-loop upper bound.

```cpp
#include <vector>
#include <functional>
using namespace std;

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        
        function<void(int)> backtrack = [&](int start) {
            if (path.size() == k) {
                result.push_back(path);
                return;
            }
            
            // Pruning: i only needs to go up to n - (k - path.size()) + 1
            for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
                path.push_back(i);
                backtrack(i + 1);
                path.pop_back();
            }
        };
        
        backtrack(1);
        return result;
    }
};

```

*Source: Adapted from `problems/0077.组合优化.md` (lines 84-106).*

### Example 2: Combination Sum III with Dual Pruning

This solution for LeetCode 216 applies both sum-based pruning and loop-range reduction to handle the constraints of selecting `k` numbers that sum to `target`.

```cpp
#include <vector>
#include <functional>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> path;
        
        function<void(int, int)> backtrack = [&](int start, int sum) {
            // Pruning 1: Sum already exceeded target
            if (sum > n) return;
            
            if (path.size() == k) {
                if (sum == n) result.push_back(path);
                return;
            }
            
            // Pruning 2: Not enough numbers left to reach k
            for (int i = start; i <= 9 - (k - path.size()) + 1; ++i) {
                path.push_back(i);
                backtrack(i + 1, sum + i);
                path.pop_back();
            }
        };
        
        backtrack(1, 0);
        return result;
    }
};

```

*Source: Adapted from `problems/0216.组合总和III.md` (lines 64-88 and 150-170).*

### Example 3: Generic Skeleton with Custom Prune Hook

This pattern demonstrates where to insert custom validation logic for problems like N-Queens or Sudoku.

```cpp
void backtrack(State &st) {
    // Custom prune: check if current state violates constraints
    if (st.isInvalid()) return;
    
    if (st.isComplete()) {
        st.storeSolution();
        return;
    }
    
    for (auto choice : st.getChoices()) {
        st.apply(choice);
        backtrack(st);
        st.revert(choice);
    }
}

```

## Summary

The backtracking template in `youngyangyang04/leetcode-master` demonstrates that **pruning is not an afterthought but an integral part of the recursive structure**. Key takeaways include:

- **Insert pruning at the termination check** to abort branches where partial sums exceed targets or states become invalid, as seen in `problems/0216.组合总和III.md`.
- **Constrain the for-loop upper bound** using mathematical bounds (`n - (k - path.size()) + 1`) to ensure sufficient elements remain for completion, documented in `problems/0077.组合优化.md`.
- **Combine multiple pruning strategies**—such as sum-checks and range-limits—to compound efficiency gains without sacrificing correctness.
- **Maintain the standard template structure** (`problems/算法模板.md`) to keep pruning logic modular and reusable across different problem types.

## Frequently Asked Questions

### What is pruning in backtracking algorithms?

**Pruning is the technique of cutting off branches in the recursion tree that cannot possibly lead to a valid solution.** In the context of the `leetcode-master` repository, pruning is implemented by adding conditional checks—such as `if (sum > target) return;` or constrained for-loop bounds—that terminate recursive exploration early when constraints are violated, significantly improving efficiency over naïve exhaustive search.

### How does loop-range pruning work in combination problems?

**Loop-range pruning limits the starting index of the for-loop to ensure enough elements remain to fill the required combination size.** As implemented in `problems/0077.组合优化.md`, the loop condition `i <= n - (k - path.size()) + 1` calculates the last valid position where the remaining slots (`k - path.size()`) can still be satisfied by the numbers left (`n - i + 1`). This prevents exploring subtrees that are guaranteed to be too short.

### Can multiple pruning strategies be used together?

**Yes, combining multiple pruning strategies is standard practice in the repository's solutions.** For example, in `problems/0216.组合总和III.md`, the algorithm applies both **sum-based pruning** (`if (sum > targetSum) return;`) to stop when the partial sum exceeds the target, and **loop-range pruning** (`i <= 9 - (k - path.size()) + 1`) to ensure sufficient elements remain. Using both simultaneously compounds the efficiency gains without adding significant code complexity.

### Where should I add custom pruning logic for problems like N-Queens or Sudoku?

**Custom pruning logic should be inserted immediately after the termination condition check but before the for-loop begins iterating over candidates.** Following the skeleton in `problems/算法模板.md`, you add a validation check—such as `if (currentState.isInvalid()) return;`—right after checking if the current state is a complete solution. This ensures that any partial state violating problem-specific constraints (like conflicting queens or duplicate numbers) is abandoned before generating child nodes.