What signals in a problem statement indicate the Partition into groups sub-pattern?

"two subsets with equal sum"; "minimum difference between the two groups"; "smash stones" (each stone ends up + or −); "k subsets with equal sum"

Partition into groups (DP — Knapsack Sub-pattern)

Q: What makes Partition into groups different from other sub-patterns?

The target isn't given — you compute it (`total / 2`). An odd total means no equal split. With k > 2 groups one capacity row isn't enough; small N (≤ 16) allows a bitmask DP.

Split the items into groups. For two groups, fixing one group's sum fixes the other's, so it becomes subset sum up to total / 2. For k groups, the state is the set of items used (bitmask).

Signals in the problem statement

›
"two subsets with equal sum"
›
"minimum difference between the two groups"
›
"smash stones" (each stone ends up + or −)
›
"k subsets with equal sum"

What makes it different

The target isn't given — you compute it (total / 2). An odd total means no equal split. With k > 2 groups one capacity row isn't enough; small N (≤ 16) allows a bitmask DP.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Partition Equal Subset Sum
Basic Anchor·LeetCode #416
WalkthroughMedium
2
Partition Into 2 Subsets with Min Sum Diff
Slight Variation·GeeksforGeeks
WalkthroughMedium
3
Last Stone Weight II
Pattern Transfer·LeetCode #1049
WalkthroughMedium
4
Partition to K Equal Sum Subsets
Tricky / Edge Case·LeetCode #698
WalkthroughMedium

Template

partition-template.cpp

// Two groups: mark every reachable subset sum up to total / 2 (0/1, high -> low).
// The other group gets total - s, so the difference is total - 2s.
int minPartitionDiff(const vector<int>& a) {
    int total = 0;
    for (int x : a) total += x;
    int half = total / 2;
    vector<bool> can(half + 1, false);
    can[0] = true;
    for (int x : a)
        for (int s = half; s >= x; s--)
            if (can[s - x]) can[s] = true;
    for (int s = half; s >= 0; s--)
        if (can[s]) return total - 2 * s;          // largest reachable s <= total / 2
    return total;
}
// Equal split: total must be even and can[total / 2] must be true.

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

Unbounded