Why Backtracking and What Greedy Cannot Solve in DSA C - Why This Pattern

Mental Model

Backtracking tries all possible choices step-by-step to find the best solution, while greedy picks the best choice at each step without looking ahead.

Analogy: Imagine choosing dishes at a buffet: greedy picks the tastiest dish first without thinking about the whole meal, but backtracking tries different combinations to make the best full meal.

Start:
Choices: [A, B, C]
Greedy picks -> A
Backtracking tries -> A -> B -> C
                      ↓    ↓    ↓
                    explore all combos

Dry Run Walkthrough

Input: Set of numbers: [3, 4, 5, 8], target sum: 7

Goal: Find if any combination of numbers sums exactly to 7

Step 1: Greedy checks nums[3]=8 > 7, skips

Sum: 0

Why: Too big for target

Step 2: Greedy picks nums[2]=5 ≤ 7

Chosen: [5]
Sum: 5

Why: Greedy picks next largest fitting

Step 3: Greedy checks nums[1]=4 > 7-5=2 skips; nums[0]=3 > 2 skips

Chosen: [5]
Sum: 5

Why: Greedy cannot add more, sum != target, fails

Step 4: Backtracking tries 3 first, sum=3 < 7, continue

Chosen: [3]
Sum: 3

Why: Backtracking explores all options

Step 5: Backtracking adds 4, sum=7 == 7, found!

Chosen: [3, 4]
Sum: 7

Why: Valid combination without the larger numbers

Result:

Greedy: No combination found
Backtracking: Found [3, 4] Sum: 7

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

bool backtrack(int nums[], int n, int target, int index, int current_sum) {
    if (current_sum == target) return true; // found exact sum
    if (current_sum > target || index == n) return false; // overshoot or no more numbers

    // choose current number
    if (backtrack(nums, n, target, index + 1, current_sum + nums[index]))
        return true;

    // skip current number
    if (backtrack(nums, n, target, index + 1, current_sum))
        return true;

    return false; // no solution found
}

bool greedy(int nums[], int n, int target) {
    int sum = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] <= target - sum) {
            sum += nums[i];
            if (sum == target) return true;
        }
    }
    return false;
}

int main() {
    int nums[] = {3, 4, 5, 8};
    int n = 4;
    int target = 7;

    if (greedy(nums, n, target))
        printf("Greedy: Found a combination summing to %d\n", target);
    else
        printf("Greedy: No combination found for %d\n", target);

    if (backtrack(nums, n, target, 0, 0))
        printf("Backtracking: Found a combination summing to %d\n", target);
    else
        printf("Backtracking: No combination found for %d\n", target);

    return 0;
}

if (current_sum == target) return true; // found exact sum

stop when exact sum is found

if (current_sum > target || index == n) return false; // overshoot or no more numbers

stop if sum too big or no more numbers

if (backtrack(nums, n, target, index + 1, current_sum + nums[index])) return true;

try including current number

if (backtrack(nums, n, target, index + 1, current_sum)) return true;

try excluding current number

for (int i = n - 1; i >= 0; i--) { if (nums[i] <= target - sum) { sum += nums[i]; if (sum == target) return true; } }

greedy picks largest numbers fitting in remaining sum

Output

Greedy: No combination found for 7

Backtracking: Found a combination summing to 7

Complexity Analysis

Time: O(2^n) because backtracking tries all subsets, greedy is O(n) because it scans once

Space: O(n) for backtracking recursion stack, O(1) for greedy

vs Alternative: Backtracking is slower but finds all solutions; greedy is fast but can miss valid combinations

Edge Cases

Empty input array

Backtracking returns false immediately; greedy returns false

DSA C

if (current_sum > target || index == n) return false;

Target sum zero

Backtracking returns true immediately; greedy returns false as no numbers needed

DSA C

if (current_sum == target) return true;

No combination sums to target

Backtracking explores all and returns false; greedy may return false early

DSA C

return false; // no solution found

When to Use This Pattern

When a problem requires exploring all possible combinations or subsets to find a valid solution, and greedy choices fail, use backtracking to try all options systematically.

Common Mistakes

Mistake: Assuming greedy always finds a solution if one exists
Fix: Use backtracking to explore all combinations when greedy fails

Mistake: Not backtracking after overshooting target sum
Fix: Add condition to stop and backtrack when sum exceeds target

Summary

Backtracking tries all possible choices to find a valid solution, while greedy picks the best immediate choice.

Use backtracking when greedy fails to find a solution because the problem requires exploring many combinations.

The key insight is that greedy can miss solutions because it never revisits earlier choices, but backtracking explores all possibilities.