The counting knapsack pattern

Every knapsack pattern has a counting version: replace opt with sum, set the base case to 1 way of making 0, and add. The subtlety is what counts as "a way".

Question	Loops	Example
combinations (order irrelevant), unlimited	items outside, totals upwards	ways to make change
ordered sequences, unlimited	totals outside, items inside	ways to climb stairs with given steps
subsets, each item once	items outside, totals downwards	subsets with a given sum
exactly k rolls or picks	an extra dimension for k	dice rolls with a target sum

Answers to counting problems grow quickly: check whether the problem asks for the count modulo 10⁹ + 7, and apply the modulus after every addition.

The problems in this module:

• Ordered ways to reach a total
• Dice rolls with a target sum
• Subsets with a given sum