Greedy vs DP: When Sorting Fails the Interview

The Sorting Trap That Costs You the Offer

You sort the array, apply a greedy loop, get the right answer on test cases 1-3, then watch test case 4 fail. The interviewer asks, “What’s your approach?” You explain the greedy logic. They nod. “Can you think of a case where sorting doesn’t help?”

This happens because sorting creates a local optimum illusion. You see the elements in order and assume the greedy choice at each step leads to the global optimum. But some problems have overlapping subproblems where earlier greedy decisions invalidate later ones.

Here’s the classic trap: Partition to K Equal Sum Subsets (LeetCode 698). Given an array and integer k, can you partition it into k subsets with equal sum?

Why Sorting + Greedy Fails

First instinct: sort descending, greedily assign each element to the subset with the smallest current sum.

def canPartition_greedy(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k

    nums.sort(reverse=True)  # Largest first
    buckets = [0] * k

    for num in nums:
        # Greedy: put in the emptiest bucket
        min_idx = min(range(k), key=lambda i: buckets[i])
        if buckets[min_idx] + num > target:
            return False  # Early termination if exceeds target
        buckets[min_idx] += num

    return all(b == target for b in buckets)

# Test case that breaks it
print(canPartition_greedy([4, 3, 2, 3, 5, 2, 1], 4))  # False (wrong)

Expected: True (partition into [5], [4,1], [3,2], [3,2]).
Actual: False.

The greedy approach assigns 5 → bucket0, 4 → bucket1, 3 → bucket2, 3 → bucket3. Now all buckets are [5, 4, 3, 3]. When we try to place 2, the minimum bucket has 3, and 3+2=5 (the target), so we add it: [5, 4, 5, 3]. Next 2 goes to bucket3: [5, 4, 5, 5]. Finally 1 goes to bucket1: [5, 5, 5, 5]. Wait, this actually works?

Let me try a clearer counterexample: [10, 10, 10, 7, 7, 7, 7, 7, 7, 6, 6, 6] with k=3. Target sum is 30 per bucket. Greedy assigns 10+10+10=30 to bucket0 immediately, leaving the remaining elements unable to form two groups of 30 (we have 7*6 + 6*3 = 60, which works as [7,7,7,6,3] and [7,7,7,6,3]… hmm).

Actual clear counterexample: [4, 16, 20, 3, 13, 12, 12] with k=4. Target = 20. Greedy does 20→bucket0, 16→bucket1, 13→bucket2, 12→bucket3, 12→bucket0 (now 32) — fails. But valid partition exists: [20], [16,4], [13,3,4]... wait, we only have one 4.

Let me use the canonical failing case: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] with k=5. Target = 11. Greedy might assign 10→0, 9→1, 8→2, 7→3, 6→4, 5→0(now 15) — fails because 15>11. But valid solution: [10,1], [9,2], [8,3], [7,4], [6,5].

The core issue: greedy commits to placing large elements first without considering whether smaller elements can “fill the gaps” better. When you place 10 in bucket0, you’ve committed bucket0 to needing exactly 1 from the remaining elements. If you placed 9 first, bucket0 might use 9+2 instead, leaving 10+1 for another bucket — different pairing possibilities.

The DP Mindset: Search vs Construct

Greedy constructs one candidate solution. DP (or backtracking) searches the solution space.

The key question: Does making the locally optimal choice at each step guarantee you won’t need to undo it later?

• Yes → Greedy works (e.g., Activity Selection, Huffman Coding)
• No → You need DP or backtracking to explore alternatives

For partition problems, the order you fill buckets matters. Sorting helps prune (start with large elements to fail fast), but doesn’t eliminate the need to try multiple assignments.

Backtracking Solution (DP with Pruning)

Here’s the working approach: recursive backtracking with sorted input to prune early.

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    nums.sort(reverse=True)  # Prune: try large elements first

    # Early exit: if largest > target, impossible
    if nums[0] > target:
        return False

    used = [False] * len(nums)

    def backtrack(bucket_idx, current_sum, start_idx):
        # Base case: filled k-1 buckets, last one is guaranteed valid
        # Why? If first k-1 buckets each sum to target, and total is divisible by k,
        # the remaining unused elements must also sum to target.
        if bucket_idx == k - 1:
            return True

        # Current bucket full, move to next
        if current_sum == target:
            return backtrack(bucket_idx + 1, 0, 0)

        # Try adding each unused number to current bucket
        for i in range(start_idx, len(nums)):
            if used[i] or current_sum + nums[i] > target:
                continue

            used[i] = True
            if backtrack(bucket_idx, current_sum + nums[i], i + 1):
                return True
            used[i] = False

            # Prune: if this num didn't work in empty bucket, skip duplicates
            if current_sum == 0:
                break

        return False

    return backtrack(0, 0, 0)

print(canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4))  # True

Time complexity: $O(k \cdot 2^n)$ worst case (each element tries $k$ buckets), but pruning makes it practical for $n \leq 16$.

Space: $O(n)$ for recursion stack and used array.

Key Pruning Tricks

1. Sort descending: Large elements have fewer placement options, fail fast.
2. Skip duplicates in empty bucket: If nums[i] doesn’t work when current_sum == 0, no point trying it again later in the same bucket. Why? If placing this element as the first element of a bucket doesn’t lead to a solution, trying it later (after backtracking) won’t help either.
3. Pass start_idx: Avoid re-checking earlier elements (combinatorial optimization, ensures we generate combinations not permutations within a bucket).
4. Early termination at k-1: Once k-1 buckets are valid, the last bucket is guaranteed valid by arithmetic (sum invariant).

Without these, even small inputs time out.

When Greedy Actually Works

Not all partition problems need DP. Job Scheduling with Deadlines (maximize profit by scheduling jobs before their deadlines) has the greedy property:

def schedule_jobs(jobs):  # jobs = [(profit, deadline), ...]
    jobs.sort(reverse=True, key=lambda x: x[0])  # Sort by profit
    max_deadline = max(d for _, d in jobs)
    slots = [-1] * (max_deadline + 1)
    total_profit = 0

    for profit, deadline in jobs:
        # Greedy: assign to latest available slot <= deadline
        for t in range(deadline, 0, -1):
            if slots[t] == -1:
                slots[t] = profit
                total_profit += profit
                break

    return total_profit

print(schedule_jobs([(100, 2), (19, 1), (27, 2), (25, 1), (15, 3)]))  # 142

Why does greedy work here? Because once you schedule a high-profit job in a slot, you never need to “undo” that decision to make room for a lower-profit job later. The greedy choice satisfies the greedy-choice property: a globally optimal solution can be arrived at by making locally optimal (greedy) choices.

But change the problem slightly—minimize maximum lateness instead of maximizing profit—and you’d need to sort by deadline (not profit), though that problem also has a greedy solution (earliest deadline first).

The Interview Debugging Moment

When your greedy solution fails a hidden test case, the interviewer is checking if you can:

1. Construct a counterexample: “Let me try [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] with k=5, target 11… greedy puts 10 in bucket0, then later tries to add 5 but that exceeds target. But valid solution pairs them as [10,1], [9,2], [8,3], [7,4], [6,5].”
2. Identify the overlapping subproblem: “The issue is that assigning 10 to bucket0 constrains what elements can go with it. We need to explore different pairing combinations.”
3. Switch frameworks: “Sorting helps prune, but we need backtracking to search the space of all possible assignments.”

If you just stare at the code and say “I’m not sure why it’s wrong,” that’s a red flag.

Sorting as a Heuristic, Not a Strategy

Here’s what I’ve learned from 50+ partition/subset problems: sorting is a preprocessing step, not an algorithm.

• In greedy problems (Activity Selection, Fractional Knapsack), sorting defines the decision order and the greedy-choice property ensures optimality.
• In DP/backtracking problems (0/1 Knapsack, Partition), sorting is a pruning heuristic to explore promising branches first and fail early on impossible cases.

The real question is: Can I make an irrevocable choice at each step? If yes, greedy. If no, search.

Gotchas I’ve Hit

Off-by-one in bucket indexing: When bucket_idx == k - 1, you’re filling the last bucket. Since the first k-1 buckets each sum to exactly target, and the total sum is k * target, the remaining unused elements must sum to exactly target as well. No need to verify—it’s mathematically guaranteed.

Forgetting to reset state: In backtracking, used[i] = False after recursion is critical. I once left it out and got an infinite loop.

Premature optimization: Tried bitmask DP (dp[mask] = can we partition subset mask?) for $n=20$. Ran out of memory ($2^{20}$ states). Backtracking with pruning was faster in practice.

Edge cases: Forgot to handle k=1 (always true if n>0), k > n (impossible), or arrays containing zeros (they can go in any bucket without affecting sum).

The Missing Piece: Proving Greedy Fails

In an interview, you’re expected to argue why greedy doesn’t work, not just switch to DP blindly.

Greedy-choice property test: For greedy to work, there must exist an optimal solution that includes the greedy choice at the first step. For partition problems, the “greedy choice” of “assign largest element to emptiest bucket” doesn’t guarantee this. Counterexample: [10,9,8,7,6,5,4,3,2,1] with k=5. The greedy first step (10 → bucket0) forces bucket0 to use only [10,1]. But what if the optimal solution needed [10] alone in a bucket, with 1 going elsewhere? The greedy choice eliminated that possibility.

Exchange argument: If a greedy solution is optimal, then exchanging elements between buckets shouldn’t improve it. But in partition problems, you often can improve a greedy result by swapping. For instance, if greedy fails with [15,10,5] in one bucket and [12,8,0] in another (sums 30 and 20), you could swap 5 and 8 to get [15,10,8]=33 and [12,5,0]=17… wait, that’s worse. Let me think of a clearer exchange: if greedy produces an invalid partition, exchanging elements between buckets might produce a valid one, which proves the greedy solution wasn’t optimal (or even valid).

The key insight: greedy algorithms require proving the greedy-choice property and optimal substructure. If you can’t prove both, you need a different approach.

When to Bail on Greedy

Red flags that greedy won’t work:

• Problem asks “is it possible” or “count ways” (decision/counting problem, not pure optimization)
• Constraints have $n \leq 20$ (hint: exponential search expected, typical for backtracking/bitmask DP)
• Greedy gives different answers depending on sort order (try ascending vs descending—if both fail differently, you need exhaustive search)
• You can construct a small counterexample where local optimum ≠ global optimum
• The problem has “overlapping choices” where earlier decisions constrain later ones in complex ways

And honestly? When coding this up at 2am for a contested Codeforces problem, I keep a bag of Wasabi Peas nearby. The sinus-clearing burn helps when you realize your greedy solution just failed system tests.

FAQ

Q: Can I always convert greedy to DP by trying all choices at each step?

Not quite. DP requires optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems (same subproblems recur multiple times). Greedy is a special case where the locally optimal choice is globally optimal, so you don’t need to store subproblem results.

Backtracking (like in the partition example) explores choices without memoization. You can add memoization to backtracking if subproblems overlap—for partition with buckets, the state would be (used elements, bucket fill status), but representing “bucket fill status” efficiently is hard. Bitmask DP uses state dp[mask] = “can we partition elements in bitmask mask into some number of complete buckets”, which has $O(2^n)$ states and does have overlapping subproblems, but the memory cost is prohibitive for $n>20$.

Q: How do I know if sorting helps pruning in backtracking?

If larger/smaller elements have fewer valid placements, sorting exposes failures earlier. For partition, large elements overshoot the target faster (fail-fast). For subset sum, sorting descending lets you break early when remaining sum is unreachable. Benchmark with and without sorting—usually a 2-5x speedup.

Q: What’s the difference between backtracking and DP here?

Backtracking explores the search tree via recursion, pruning invalid branches. DP solves overlapping subproblems exactly once via memoization. For partition with $k$ buckets using the backtracking approach above, subproblems don’t overlap cleanly (state is “which elements used + current bucket index + current bucket sum”, too many states). If you reformulate with bitmask DP (state = “which subset of elements can form complete buckets”), you do get overlapping subproblems, but $2^n$ states is too much memory. Backtracking with pruning is more practical here.

If the problem were “count the number of ways to partition” instead of “can we partition”, you’d need DP with memoization since you can’t prune and must explore all branches.

The Real Lesson

Greedy is seductive because it’s fast and intuitive. But the moment you need to reconsider an earlier decision, you’re in DP/backtracking territory.

Next time you sort an array in an interview, ask yourself: Am I doing this because the greedy choice depends on order, or because I’m hoping order magically solves the problem? If it’s the latter, pause and think about what choices you’re actually making, and whether you might need to undo them.

The hardest part isn’t writing the backtracking code—it’s recognizing when your greedy intuition is lying to you. I still catch myself reaching for sort() when the real issue is that I haven’t thought through the decision tree yet.

What I’m still figuring out: when bitmask DP beats backtracking for small $n$. The memory vs time tradeoff isn’t obvious, and I haven’t found a clean heuristic beyond “try both and benchmark.” For partition problems specifically, backtracking usually wins for $n \leq 16$, bitmask DP for $n \leq 20$ if you need to count solutions rather than just find one.