Greedy Algorithms and Backtracking

📖 Introduction

Greedy algorithms and backtracking represent two fundamental approaches to problem-solving that I use constantly. Greedy is about making the locally optimal choice at each step, hoping it leads to a global optimum. Backtracking is about systematically exploring all possibilities.

Understanding when each approach applies—and when it doesn't—has saved me countless hours. A problem that seems to need backtracking might have a greedy solution, and vice versa.

---

🟢 Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, never reconsidering past decisions.

When Greedy Works

Greedy Choice Property: A globally optimal solution can be reached by selecting the locally optimal choice.

Optimal Substructure: An optimal solution contains optimal solutions to subproblems.

---

📊 Classic Greedy Problems

Activity Selection

def max_activities(start: list[int], end: list[int]) -> list[int]:
    """
    Select maximum non-overlapping activities.
    Greedy: Always pick activity that ends earliest.
    Time: O(n log n)
    """
    n = len(start)
    activities = sorted(range(n), key=lambda i: end[i])
    
    result = [activities[0]]
    last_end = end[activities[0]]
    
    for i in activities[1:]:
        if start[i] >= last_end:
            result.append(i)
            last_end = end[i]
    
    return result


# Example
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
print(max_activities(start, end))  # [0, 1, 3, 4]

Jump Game

def can_jump(nums: list[int]) -> bool:
    """
    Can you reach the last index?
    nums[i] = max jump from position i.
    Greedy: Track farthest reachable position.
    """
    farthest = 0
    
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
        
        if farthest >= len(nums) - 1:
            return True
    
    return True


def jump_min_steps(nums: list[int]) -> int:
    """
    Minimum jumps to reach last index.
    Greedy: Jump to position that maximizes next reach.
    """
    if len(nums) <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            current_end = farthest
    
    return jumps

Gas Station

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    """
    Find starting station for circular route.
    Greedy: If total gas >= total cost, solution exists.
    Start from station after we run out.
    """
    total_tank = 0
    current_tank = 0
    start = 0
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        if current_tank < 0:
            start = i + 1
            current_tank = 0
    
    return start if total_tank >= 0 else -1

Task Scheduler

from collections import Counter

def least_interval(tasks: list[str], n: int) -> int:
    """
    Minimum intervals to complete all tasks.
    Same task needs n intervals apart.
    Greedy: Schedule most frequent tasks first.
    """
    counts = Counter(tasks)
    max_count = max(counts.values())
    
    # Tasks with maximum frequency
    max_count_tasks = sum(1 for c in counts.values() if c == max_count)
    
    # Minimum time needed
    result = (max_count - 1) * (n + 1) + max_count_tasks
    
    return max(result, len(tasks))

Partition Labels

def partition_labels(s: str) -> list[int]:
    """
    Partition string so each letter appears in at most one part.
    Greedy: Track last occurrence of each character.
    """
    last = {c: i for i, c in enumerate(s)}
    
    result = []
    start = end = 0
    
    for i, c in enumerate(s):
        end = max(end, last[c])
        
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    
    return result


print(partition_labels("ababcbacadefegdehijhklij"))
# [9, 7, 8]

Non-overlapping Intervals

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    """
    Minimum intervals to remove for no overlap.
    Greedy: Keep interval that ends earliest.
    """
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[1])
    
    count = 0
    end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] < end:
            count += 1  # Remove this interval
        else:
            end = intervals[i][1]
    
    return count

Candy

def candy(ratings: list[int]) -> int:
    """
    Give candies to children based on ratings.
    Each child gets at least 1.
    Higher rating than neighbor = more candy.
    Greedy: Two passes (left to right, right to left).
    """
    n = len(ratings)
    candies = [1] * n
    
    # Left to right
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    
    # Right to left
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    
    return sum(candies)

---

⚠️ Greedy Pitfalls

When Greedy Fails

# Coin change - greedy fails for some denominations
def coin_change_greedy(coins: list[int], amount: int) -> int:
    """
    WRONG for some cases!
    """
    coins.sort(reverse=True)
    count = 0
    
    for coin in coins:
        count += amount // coin
        amount %= coin
    
    return count if amount == 0 else -1


# Greedy: coins = [1, 3, 4], amount = 6 → 4+1+1 = 3 coins
# Optimal: 3+3 = 2 coins

---

🔙 Backtracking

Backtracking explores all possibilities by building solutions incrementally and abandoning (backtracking from) solutions that don't satisfy constraints.

Backtracking Template

def backtrack_template(candidates, path, result):
    """
    General backtracking pattern.
    """
    if is_solution(path):
        result.append(path[:])  # Add copy
        return
    
    for candidate in candidates:
        if is_valid(candidate, path):
            path.append(candidate)  # Make choice
            backtrack_template(candidates, path, result)  # Explore
            path.pop()  # Undo choice (backtrack)

---

📊 Backtracking Problems

Subsets

def subsets(nums: list[int]) -> list[list[int]]:
    """
    Generate all subsets.
    Time: O(2^n * n)
    """
    result = []
    
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result


# With duplicates
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """Handle duplicates by sorting and skipping."""
    result = []
    nums.sort()
    
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            # Skip duplicates
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

Permutations

def permutations(nums: list[int]) -> list[list[int]]:
    """
    Generate all permutations.
    Time: O(n! * n)
    """
    result = []
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    
    backtrack([], nums)
    return result


# In-place using swapping
def permutations_swap(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    
    backtrack(0)
    return result


# With duplicates
def permutations_unique(nums: list[int]) -> list[list[int]]:
    result = []
    nums.sort()
    used = [False] * len(nums)
    
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip duplicates
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    
    backtrack([])
    return result

Combinations

def combinations(n: int, k: int) -> list[list[int]]:
    """
    Generate all combinations of k numbers from [1, n].
    Time: O(C(n,k) * k)
    """
    result = []
    
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        
        # Pruning: not enough numbers left
        remaining = n - start + 1
        needed = k - len(path)
        if remaining < needed:
            return
        
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(1, [])
    return result

Combination Sum

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """
    Find all combinations that sum to target.
    Each number can be used unlimited times.
    """
    result = []
    
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return
        
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1
            path.pop()
    
    backtrack(0, [], target)
    return result


# Each number used once
def combination_sum_once(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    candidates.sort()
    
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            # Skip duplicates
            if i > start and candidates[i] == candidates[i-1]:
                continue
            
            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])
            path.pop()
    
    backtrack(0, [], target)
    return result

N-Queens

def solve_n_queens(n: int) -> list[list[str]]:
    """
    Place n queens on n×n board with no attacks.
    """
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    
    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if col in cols or row - col in diag1 or row + col in diag2:
                continue
            
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            backtrack(row + 1)
            
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result

Sudoku Solver

def solve_sudoku(board: list[list[str]]) -> None:
    """
    Solve Sudoku in-place.
    """
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    
    # Initialize sets and find empty cells
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                empty.append((i, j))
            else:
                num = board[i][j]
                rows[i].add(num)
                cols[j].add(num)
                boxes[(i // 3) * 3 + j // 3].add(num)
    
    def backtrack(idx):
        if idx == len(empty):
            return True
        
        i, j = empty[idx]
        box_idx = (i // 3) * 3 + j // 3
        
        for num in '123456789':
            if num in rows[i] or num in cols[j] or num in boxes[box_idx]:
                continue
            
            board[i][j] = num
            rows[i].add(num)
            cols[j].add(num)
            boxes[box_idx].add(num)
            
            if backtrack(idx + 1):
                return True
            
            board[i][j] = '.'
            rows[i].remove(num)
            cols[j].remove(num)
            boxes[box_idx].remove(num)
        
        return False
    
    backtrack(0)

Word Search

def exist(board: list[list[str]], word: str) -> bool:
    """
    Find if word exists in grid (adjacent cells, no reuse).
    """
    rows, cols = len(board), len(board[0])
    
    def backtrack(i, j, k):
        if k == len(word):
            return True
        
        if (i < 0 or i >= rows or 
            j < 0 or j >= cols or 
            board[i][j] != word[k]):
            return False
        
        # Mark as visited
        temp = board[i][j]
        board[i][j] = '#'
        
        # Explore neighbors
        found = (backtrack(i + 1, j, k + 1) or
                 backtrack(i - 1, j, k + 1) or
                 backtrack(i, j + 1, k + 1) or
                 backtrack(i, j - 1, k + 1))
        
        # Restore
        board[i][j] = temp
        
        return found
    
    for i in range(rows):
        for j in range(cols):
            if backtrack(i, j, 0):
                return True
    
    return False

---

🎯 Pruning Strategies

Pruning reduces the search space by eliminating branches that can't lead to valid solutions.

def combination_sum_pruned(candidates: list[int], target: int) -> list[list[int]]:
    """
    With sorting and pruning for efficiency.
    """
    result = []
    candidates.sort()  # Enable pruning
    
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            # Pruning: if current > remaining, all following will be too
            if candidates[i] > remaining:
                break
            
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])
            path.pop()
    
    backtrack(0, [], target)
    return result

---

📝 Practice Exercises

Exercise 1: Restore IP Addresses

def restore_ip_addresses(s: str) -> list[str]:
    """
    Return all valid IP addresses from string.
    
    "25525511135" -> ["255.255.11.135", "255.255.111.35"]
    """
    pass

Solution

def restore_ip_addresses(s: str) -> list[str]:
    result = []
    
    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                result.append('.'.join(parts))
            return
        
        for length in range(1, 4):
            if start + length > len(s):
                break
            
            segment = s[start:start + length]
            
            # Skip leading zeros (except "0")
            if len(segment) > 1 and segment[0] == '0':
                continue
            
            if int(segment) > 255:
                continue
            
            parts.append(segment)
            backtrack(start + length, parts)
            parts.pop()
    
    backtrack(0, [])
    return result

Exercise 2: Generate Parentheses

def generate_parenthesis(n: int) -> list[str]:
    """
    Generate all valid combinations of n pairs of parentheses.
    
    n = 3 -> ["((()))", "(()())", "(())()", "()(())", "()()()"]
    """
    pass

Solution

def generate_parenthesis(n: int) -> list[str]:
    result = []
    
    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return
        
        if open_count < n:
            path.append('(')
            backtrack(path, open_count + 1, close_count)
            path.pop()
        
        if close_count < open_count:
            path.append(')')
            backtrack(path, open_count, close_count + 1)
            path.pop()
    
    backtrack([], 0, 0)
    return result

Exercise 3: Minimum Number of Arrows

def find_min_arrow_shots(points: list[list[int]]) -> int:
    """
    Balloons as horizontal intervals.
    Arrow at x bursts balloon if x_start <= x <= x_end.
    Find minimum arrows to burst all balloons.
    
    [[10,16],[2,8],[1,6],[7,12]] -> 2
    """
    pass

Solution

def find_min_arrow_shots(points: list[list[int]]) -> int:
    if not points:
        return 0
    
    # Sort by end position
    points.sort(key=lambda x: x[1])
    
    arrows = 1
    current_end = points[0][1]
    
    for start, end in points[1:]:
        if start > current_end:
            arrows += 1
            current_end = end
    
    return arrows

---

🔑 Key Takeaways

1. Greedy works when local optimal leads to global optimal

2. Verify greedy correctness or use DP if unsure

3. Backtracking systematically explores all possibilities

4. Template: make choice → explore → undo choice

5. Pruning is essential for backtracking efficiency

6. Sort first when order helps (both greedy and backtracking)

---

🚀 What's Next?

In the next article, we'll explore graph algorithms:

• Shortest path algorithms (Dijkstra, Bellman-Ford)

• Minimum spanning tree (Prim, Kruskal)

• Topological sort

• Union-Find data structure

Next: Article 14 - Graph Algorithms

---

📚 References

• CLRS Chapter 16: Greedy Algorithms

• "Algorithm Design" - Kleinberg & Tardos

• LeetCode Backtracking patterns