What signals in a problem statement indicate the Count ways sub-pattern?

"number of subsets with sum X"; "number of ways to assign + and −"; "count the schemes", "return it modulo 10⁹ + 7"

Count ways (DP — Knapsack Sub-pattern)

Q: What makes Count ways different from other sub-patterns?

`dp[0] = 1`, not 0 — there is exactly one way to make sum 0 (take nothing). Zeros in the input double the count, and the table handles that by itself.

Same 0/1 table, but cells hold counts and the combine step is +: the subsets that skip the item plus the subsets that take it.

Signals in the problem statement

›
"number of subsets with sum X"
›
"number of ways to assign + and −"
›
"count the schemes", "return it modulo 10⁹ + 7"

What makes it different

dp[0] = 1, not 0 — there is exactly one way to make sum 0 (take nothing). Zeros in the input double the count, and the table handles that by itself.

Questions

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

1
Count Subsets with Sum
Basic Anchor·GeeksforGeeks
WalkthroughMedium
2
Target Sum
Pattern Transfer·LeetCode #494
WalkthroughMedium
3
Profitable Schemes
Interview-Level·LeetCode #879
WalkthroughHard

Template

count-ways-template.cpp

// Count subsets with sum = target: same 0/1 row, but add counts.
// dp[s] = number of subsets of the items so far with sum s.
int countSubsets(const vector<int>& a, int target) {
    const int MOD = 1e9 + 7;
    vector<long long> dp(target + 1, 0);
    dp[0] = 1;                                     // the empty subset
    for (int x : a)
        for (int s = target; s >= x; s--)          // high -> low: each item once
            dp[s] = (dp[s] + dp[s - x]) % MOD;     // without x + with x
    return (int)dp[target];
}

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)?

0/1 knapsack Unbounded