Identifying the counting knapsack pattern

The counting knapsack pattern solves problems where the input is a set of items and a capacity, and the answer is the number of ways the items can fill the capacity exactly. These are generally medium problems where we decide the items one at a time, and everything the problem counts is assembled along a path of these decisions.

When a problem statement, or its natural recursive solution, matches the template below, it is a counting knapsack problem.

Template

Given n items and a capacity C, compute dp(i, c), the number of ways to fill exactly the capacity c from the items 0 through i, for each item index i and each remaining capacity 0 <= c <= C where each item can be picked an unlimited number of times.

How to identify the counting knapsack pattern

There are two signals that tell us if problem is a counting knapsack problem, and once we identify them, the flavour of the count must be deduced from the problem to build the correct solution for it.

A set of items and a target to assemble

If the input is a collection of items, each with a size, together with a target amount, and the goal is to select items with sizes that total the target exactly, the problem is generally a knapsack problem. Words like make up the amount, sum to the target, or exactly equal point to this input.

Note that the supply of the items can be bounded or unbounded.