Problem-Solving Strategies - Learning Module

Loading content...

0/276

Breaking Down Problems into Smaller Instances

The Art of Problem Decomposition

Once you've identified that a problem has recursive structure, the next critical step is defining exactly how it decomposes. This isn't automatic—even problems with obvious recursive potential can be decomposed in multiple ways, each with different implications for correctness, efficiency, and code clarity.

Problem decomposition is where recursive thinking transforms from recognition into design. A skilled recursive thinker doesn't just see that a problem can be broken down—they see how it should be broken down to yield the most elegant, efficient solution.

This page develops your decomposition instincts, teaching you to see the natural fault lines in problems and split them cleanly into subproblems that recombine seamlessly.

What You Will Learn

By mastering this page, you will: (1) Understand the principles of effective problem decomposition, (2) Learn multiple decomposition strategies and when to apply each, (3) Develop skills to identify the optimal subproblem structure, (4) Practice decomposing real problems into recursive subproblems.

Principles of Effective Decomposition

Not all decompositions are equal. An effective recursive decomposition satisfies several key principles:

Principle 1: Subproblems Must Be Strictly Smaller

Every recursive call must operate on a demonstrably smaller input. 'Smaller' can mean:

Fewer elements (array shrinks)
Lower value (n decreases)
Reduced depth (tree shrinks toward leaves)
Fewer remaining choices (possibilities narrow)

The size reduction must be guaranteed on every path, not just some paths. A decomposition that sometimes doesn't shrink the problem leads to infinite recursion.

Principle 2: Subproblems Must Be Well-Defined

Each subproblem should be a complete, self-contained instance of the problem type. The subproblem shouldn't need external context that isn't explicitly passed to it.

Principle 3: Subproblems Should Be Independent (When Possible)

The cleanest decompositions create independent subproblems—solving one doesn't affect another. This enables both conceptual clarity and potential parallelization.

The Four Questions of Decomposition

•What shrinks? — Identify the dimension of the problem that decreases with each recursive call. Array length? Numeric value? Tree height? Remaining choices?
•How many subproblems? — Does the problem split into one subproblem (linear recursion), two (binary recursion), or many (k-way recursion)?
•What context passes down? — What additional information do subproblems need beyond the smaller input? Bounds? Accumulated state? Constraints?
•How do results combine? — How do subproblem solutions assemble into the full solution? Addition? Concatenation? Selection? More complex merging?

Decomposition Strategies

Different problem types call for different decomposition strategies. Here are the major approaches:

Strategy 1: Peel-One-Off (Linear Decomposition)

The simplest strategy: handle one element, recurse on the rest.

Pattern: solve(all) = combine(first, solve(rest))

Examples:

Sum of list: sum([a, ...rest]) = a + sum(rest)
String reversal: reverse(s) = reverse(s[1:]) + s[0]
Linked list operations: process head, recurse on tail

When to use: Sequential processing where each element is handled independently.

Strategy 2: Divide-in-Half (Binary Decomposition)

Split the problem into two roughly equal parts, solve each, combine.

Pattern: solve(all) = combine(solve(left_half), solve(right_half))

Examples:

Merge sort: sort left, sort right, merge
Binary search: search left OR right based on comparison
Tree traversal: process left subtree, process right subtree

When to use: When halving provides logarithmic depth benefits or when the problem has natural binary structure.

decomposition_strategies
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Strategy 1: Peel-One-Off (Linear)
function sumArray(arr: number[]): number {
    if (arr.length === 0) return 0;
    // Handle first, recurse on rest
    return arr[0] + sumArray(arr.slice(1));
}
 
// Strategy 2: Divide-in-Half (Binary)
function maxElement(arr: number[]): number {
    if (arr.length === 1) return arr[0];
    
    const mid = Math.floor(arr.length / 2);
    const leftMax = maxElement(arr.slice(0, mid));
    const rightMax = maxElement(arr.slice(mid));
    
    return Math.max(leftMax, rightMax);
}
 
// Strategy 3: Choice-Based (Branching)
function subsets(nums: number[]): number[][] {
    if (nums.length === 0) return [[]];
    
    const first = nums[0];
    const restSubsets = subsets(nums.slice(1));
    
    // Each subset spawns two: with and without first
    const result: number[][] = [];
    for (const sub of restSubsets) {
        result.push(sub);           // Without first
        result.push([first, ...sub]); // With first
    }
    return result;
}

Strategy 3: Choice-Based (Branching Decomposition)

At each step, enumerate choices; each choice leads to a subproblem.

Pattern: solve(state) = for each choice: solve(state_after_choice)

Examples:

Permutations: for each unused element, place it next and permute rest
Pathfinding: for each valid direction, find path from new position
Game trees: for each legal move, evaluate resulting position

When to use: Combinatorial problems, search problems, games.

Strategy 4: Range-Based (Interval Decomposition)

Define subproblems over ranges or intervals of the input.

Pattern: solve(i, j) = combine(solve(i, k), solve(k+1, j)) for some k

Examples:

Matrix chain multiplication
Optimal BST construction
Palindrome partitioning

When to use: Optimization over contiguous sequences where split point matters.

Choosing the Right Decomposition

The same problem can often be decomposed multiple ways. How do you choose?

Factor 1: Natural Structure of the Data

Let the data guide you:

Trees → Binary decomposition (left/right subtrees)
Lists/Arrays → Linear (peel-one-off) or binary (halve)
Strings with choices → Choice-based
Intervals → Range-based

Factor 2: Complexity Implications

Different decompositions yield different time complexities:

Linear decomposition: typically O(n) depth, O(n) or O(n²) time
Binary decomposition: O(log n) depth, often O(n log n) time
Choice-based: often exponential (but necessary for those problems)

Factor 3: Code Clarity

Sometimes multiple decompositions have similar performance. Choose the one that produces the clearest code—the one where the recursive structure most naturally mirrors the problem statement.

Decomposition Strategy Selection Guide
Problem Type	Recommended Strategy	Typical Complexity	Example
Sequential processing	Peel-one-off	O(n)	Sum, reverse, filter
Divide-and-conquer sorting	Divide-in-half	O(n log n)	Merge sort, quick sort
Search in sorted data	Divide-in-half	O(log n)	Binary search
Generate all combinations	Choice-based	O(2^n)	Subsets, permutations
Optimal splitting	Range-based	O(n³) typically	Matrix chain, optimal BST

The Natural Decomposition Test

If you find yourself adding complex bookkeeping or fighting the problem structure, you might have chosen the wrong decomposition. Step back and ask: 'Is there a more natural way to split this?' The right decomposition usually feels effortless.

Passing Context to Subproblems

Often, subproblems need more than just the smaller input—they need context about what came before or constraints that must be maintained.

Common Context Types

1. Accumulated State: Information gathered during descent

Running sum, current path, collected results
Example: Finding all root-to-leaf paths (pass current path down)

2. Constraints/Bounds: Limits that subproblems must respect

Min/max valid values, remaining budget, position constraints
Example: BST validation (pass valid range down)

3. Parent Information: Data about ancestors in the call tree

Parent node, depth level, ancestor values
Example: Finding lowest common ancestor

4. Configuration: Settings that affect how subproblems should be solved

Search direction, optimization goal, processing mode

context_passing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
interface TreeNode {
    value: number;
    left?: TreeNode;
    right?: TreeNode;
}
 
// Example 1: Accumulated State - collect all root-to-leaf paths
function allPaths(node: TreeNode | undefined, currentPath: number[] = []): number[][] {
    if (!node) return [];
    
    const pathWithCurrent = [...currentPath, node.value];
    
    // Leaf node: return the complete path
    if (!node.left && !node.right) {
        return [pathWithCurrent];
    }
    
    // Internal node: collect paths from both subtrees
    return [
        ...allPaths(node.left, pathWithCurrent),
        ...allPaths(node.right, pathWithCurrent),
    ];
}
 
// Example 2: Constraints - validate BST with bounds
function isValidBST(
    node: TreeNode | undefined,
    min = -Infinity,
    max = Infinity
): boolean {
    if (!node) return true;
    if (node.value <= min || node.value >= max) return false;
    
    // Pass tightened bounds to subtrees
    return (
        isValidBST(node.left, min, node.value) &&
        isValidBST(node.right, node.value, max)
    );
}
 
// Example 3: Parent info - find depth of each node
function labelDepths(node: TreeNode | undefined, depth = 0): Map<number, number> {
    if (!node) return new Map();
    
    const result = new Map<number, number>();
    result.set(node.value, depth);
    
    // Pass incremented depth to children
    for (const [val, d] of labelDepths(node.left, depth + 1)) {
        result.set(val, d);
    }
    for (const [val, d] of labelDepths(node.right, depth + 1)) {
        result.set(val, d);
    }
    
    return result;
}

Helper Functions for Clean Signatures

When context parameters make your function signature complex, use a pattern with a public wrapper and private helper. The public function has a clean signature; the helper carries all the context. This keeps your API clean while enabling full context passing internally.

Common Decomposition Patterns

Certain decomposition patterns appear repeatedly across different problems. Internalizing these patterns accelerates your problem solving.

Pattern 1: First/Rest Decomposition

f([first, ...rest]) = combine(first, f(rest))
Base: f([]) = identity

Used for: list processing, string operations, sequential decisions.

Pattern 2: Left/Right Decomposition

f(arr) = combine(f(arr[0:mid]), f(arr[mid:]))
Base: f([single]) or f([])

Used for: divide-and-conquer, tree operations, balanced processing.

Pattern 3: Include/Exclude Decomposition

f(item, rest) = combine(f_with_item(rest), f_without_item(rest))
Base: no items left

Used for: subset generation, knapsack problems, decision trees.

Pattern 4: Choose-and-Continue

f(state) = for each valid_choice: f(state + choice)
Base: state is complete/terminal

Used for: permutations, pathfinding, game search, backtracking.

Decomposition Pattern Quick Reference
Pattern	Subproblems	Base Case	Classic Examples
First/Rest	1 (rest of list)	Empty list	Sum, reverse, map
Left/Right	2 (halves)	Single/empty	Merge sort, max
Include/Exclude	2 (branches)	No items	Subsets, knapsack
Choose-and-Continue	k (choices)	Goal reached	Permutations, N-queens

Summary: Key Takeaways

Core Principles

•Effective decomposition requires strict shrinking — Every recursive call must operate on demonstrably smaller input.
•Four key strategies — Peel-one-off (linear), divide-in-half (binary), choice-based (branching), and range-based (intervals).
•Let data structure guide strategy — Trees suggest binary, lists suggest linear or binary, choices suggest branching.
•Context enables complex recursion — Pass accumulated state, constraints, or parent info as needed.
•Know the patterns — First/rest, left/right, include/exclude, and choose-and-continue cover most cases.

Page Complete

You now understand how to decompose problems into recursive subproblems effectively. The next page covers building solutions from smaller solutions—how subproblem results combine into final answers.

Breaking Down Problems into Smaller Instances

The Art of Problem Decomposition

This page develops your decomposition instincts, teaching you to see the natural fault lines in problems and split them cleanly into subproblems that recombine seamlessly.

What You Will Learn

Principles of Effective Decomposition

Not all decompositions are equal. An effective recursive decomposition satisfies several key principles:

Principle 1: Subproblems Must Be Strictly Smaller

Every recursive call must operate on a demonstrably smaller input. 'Smaller' can mean:

Fewer elements (array shrinks)
Lower value (n decreases)
Reduced depth (tree shrinks toward leaves)
Fewer remaining choices (possibilities narrow)

The size reduction must be guaranteed on every path, not just some paths. A decomposition that sometimes doesn't shrink the problem leads to infinite recursion.

Principle 2: Subproblems Must Be Well-Defined

Each subproblem should be a complete, self-contained instance of the problem type. The subproblem shouldn't need external context that isn't explicitly passed to it.

Principle 3: Subproblems Should Be Independent (When Possible)

The cleanest decompositions create independent subproblems—solving one doesn't affect another. This enables both conceptual clarity and potential parallelization.

The Four Questions of Decomposition

•What shrinks? — Identify the dimension of the problem that decreases with each recursive call. Array length? Numeric value? Tree height? Remaining choices?
•How many subproblems? — Does the problem split into one subproblem (linear recursion), two (binary recursion), or many (k-way recursion)?
•What context passes down? — What additional information do subproblems need beyond the smaller input? Bounds? Accumulated state? Constraints?
•How do results combine? — How do subproblem solutions assemble into the full solution? Addition? Concatenation? Selection? More complex merging?

Decomposition Strategies

Different problem types call for different decomposition strategies. Here are the major approaches:

Strategy 1: Peel-One-Off (Linear Decomposition)

The simplest strategy: handle one element, recurse on the rest.

Pattern: solve(all) = combine(first, solve(rest))

Examples:

Sum of list: sum([a, ...rest]) = a + sum(rest)
String reversal: reverse(s) = reverse(s[1:]) + s[0]
Linked list operations: process head, recurse on tail

When to use: Sequential processing where each element is handled independently.

Strategy 2: Divide-in-Half (Binary Decomposition)

Split the problem into two roughly equal parts, solve each, combine.

Pattern: solve(all) = combine(solve(left_half), solve(right_half))

Examples:

Merge sort: sort left, sort right, merge
Binary search: search left OR right based on comparison
Tree traversal: process left subtree, process right subtree

When to use: When halving provides logarithmic depth benefits or when the problem has natural binary structure.

decomposition_strategies
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Strategy 1: Peel-One-Off (Linear)
function sumArray(arr: number[]): number {
    if (arr.length === 0) return 0;
    // Handle first, recurse on rest
    return arr[0] + sumArray(arr.slice(1));
}
 
// Strategy 2: Divide-in-Half (Binary)
function maxElement(arr: number[]): number {
    if (arr.length === 1) return arr[0];
    
    const mid = Math.floor(arr.length / 2);
    const leftMax = maxElement(arr.slice(0, mid));
    const rightMax = maxElement(arr.slice(mid));
    
    return Math.max(leftMax, rightMax);
}
 
// Strategy 3: Choice-Based (Branching)
function subsets(nums: number[]): number[][] {
    if (nums.length === 0) return [[]];
    
    const first = nums[0];
    const restSubsets = subsets(nums.slice(1));
    
    // Each subset spawns two: with and without first
    const result: number[][] = [];
    for (const sub of restSubsets) {
        result.push(sub);           // Without first
        result.push([first, ...sub]); // With first
    }
    return result;
}

Strategy 3: Choice-Based (Branching Decomposition)

At each step, enumerate choices; each choice leads to a subproblem.

Pattern: solve(state) = for each choice: solve(state_after_choice)

Examples:

Permutations: for each unused element, place it next and permute rest
Pathfinding: for each valid direction, find path from new position
Game trees: for each legal move, evaluate resulting position

When to use: Combinatorial problems, search problems, games.

Strategy 4: Range-Based (Interval Decomposition)

Define subproblems over ranges or intervals of the input.

Pattern: solve(i, j) = combine(solve(i, k), solve(k+1, j)) for some k

Examples:

Matrix chain multiplication
Optimal BST construction
Palindrome partitioning

When to use: Optimization over contiguous sequences where split point matters.

Choosing the Right Decomposition

The same problem can often be decomposed multiple ways. How do you choose?

Factor 1: Natural Structure of the Data

Let the data guide you:

Trees → Binary decomposition (left/right subtrees)
Lists/Arrays → Linear (peel-one-off) or binary (halve)
Strings with choices → Choice-based
Intervals → Range-based

Factor 2: Complexity Implications

Different decompositions yield different time complexities:

Linear decomposition: typically O(n) depth, O(n) or O(n²) time
Binary decomposition: O(log n) depth, often O(n log n) time
Choice-based: often exponential (but necessary for those problems)

Factor 3: Code Clarity

Sometimes multiple decompositions have similar performance. Choose the one that produces the clearest code—the one where the recursive structure most naturally mirrors the problem statement.

Decomposition Strategy Selection Guide
Problem Type	Recommended Strategy	Typical Complexity	Example
Sequential processing	Peel-one-off	O(n)	Sum, reverse, filter
Divide-and-conquer sorting	Divide-in-half	O(n log n)	Merge sort, quick sort
Search in sorted data	Divide-in-half	O(log n)	Binary search
Generate all combinations	Choice-based	O(2^n)	Subsets, permutations
Optimal splitting	Range-based	O(n³) typically	Matrix chain, optimal BST

The Natural Decomposition Test

Passing Context to Subproblems

Often, subproblems need more than just the smaller input—they need context about what came before or constraints that must be maintained.

Common Context Types

1. Accumulated State: Information gathered during descent

Running sum, current path, collected results
Example: Finding all root-to-leaf paths (pass current path down)

2. Constraints/Bounds: Limits that subproblems must respect

Min/max valid values, remaining budget, position constraints
Example: BST validation (pass valid range down)

3. Parent Information: Data about ancestors in the call tree

Parent node, depth level, ancestor values
Example: Finding lowest common ancestor

4. Configuration: Settings that affect how subproblems should be solved

Search direction, optimization goal, processing mode

context_passing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
interface TreeNode {
    value: number;
    left?: TreeNode;
    right?: TreeNode;
}
 
// Example 1: Accumulated State - collect all root-to-leaf paths
function allPaths(node: TreeNode | undefined, currentPath: number[] = []): number[][] {
    if (!node) return [];
    
    const pathWithCurrent = [...currentPath, node.value];
    
    // Leaf node: return the complete path
    if (!node.left && !node.right) {
        return [pathWithCurrent];
    }
    
    // Internal node: collect paths from both subtrees
    return [
        ...allPaths(node.left, pathWithCurrent),
        ...allPaths(node.right, pathWithCurrent),
    ];
}
 
// Example 2: Constraints - validate BST with bounds
function isValidBST(
    node: TreeNode | undefined,
    min = -Infinity,
    max = Infinity
): boolean {
    if (!node) return true;
    if (node.value <= min || node.value >= max) return false;
    
    // Pass tightened bounds to subtrees
    return (
        isValidBST(node.left, min, node.value) &&
        isValidBST(node.right, node.value, max)
    );
}
 
// Example 3: Parent info - find depth of each node
function labelDepths(node: TreeNode | undefined, depth = 0): Map<number, number> {
    if (!node) return new Map();
    
    const result = new Map<number, number>();
    result.set(node.value, depth);
    
    // Pass incremented depth to children
    for (const [val, d] of labelDepths(node.left, depth + 1)) {
        result.set(val, d);
    }
    for (const [val, d] of labelDepths(node.right, depth + 1)) {
        result.set(val, d);
    }
    
    return result;
}

Helper Functions for Clean Signatures

Common Decomposition Patterns

Certain decomposition patterns appear repeatedly across different problems. Internalizing these patterns accelerates your problem solving.

Pattern 1: First/Rest Decomposition

f([first, ...rest]) = combine(first, f(rest))
Base: f([]) = identity

Used for: list processing, string operations, sequential decisions.

Pattern 2: Left/Right Decomposition

f(arr) = combine(f(arr[0:mid]), f(arr[mid:]))
Base: f([single]) or f([])

Used for: divide-and-conquer, tree operations, balanced processing.

Pattern 3: Include/Exclude Decomposition

f(item, rest) = combine(f_with_item(rest), f_without_item(rest))
Base: no items left

Used for: subset generation, knapsack problems, decision trees.

Pattern 4: Choose-and-Continue

f(state) = for each valid_choice: f(state + choice)
Base: state is complete/terminal

Used for: permutations, pathfinding, game search, backtracking.

Decomposition Pattern Quick Reference
Pattern	Subproblems	Base Case	Classic Examples
First/Rest	1 (rest of list)	Empty list	Sum, reverse, map
Left/Right	2 (halves)	Single/empty	Merge sort, max
Include/Exclude	2 (branches)	No items	Subsets, knapsack
Choose-and-Continue	k (choices)	Goal reached	Permutations, N-queens

Summary: Key Takeaways

Core Principles

•Effective decomposition requires strict shrinking — Every recursive call must operate on demonstrably smaller input.
•Four key strategies — Peel-one-off (linear), divide-in-half (binary), choice-based (branching), and range-based (intervals).
•Let data structure guide strategy — Trees suggest binary, lists suggest linear or binary, choices suggest branching.
•Context enables complex recursion — Pass accumulated state, constraints, or parent info as needed.
•Know the patterns — First/rest, left/right, include/exclude, and choose-and-continue cover most cases.

Page Complete