Count the picks that hit an exact total

Walk the items in order and, for each, branch into 'take it' and 'skip it'. Stop a branch as soon as the running total equals the goal (count it) or passes it (prune it). Without pruning this is O(2ⁿ) time with O(n) recursion depth; pruning cuts that sharply on real inputs. For large goals with small prices, a DP table over totals is faster.

This is the include-or-skip template behind most selection questions.

Pruning on 'total > goal' is valid only because prices are positive.

Sorting prices ascending lets you break out of a loop early, a stronger prune.

def count_picks(prices: list[int], goal: int) -> int:
    def walk(i: int, total: int) -> int:
        if total == goal:
            return 1  # adding more positive prices only overshoots
        if total > goal or i == len(prices):
            return 0  # pruned or out of items
        take = walk(i + 1, total + prices[i])
        return take + walk(i + 1, total)
    return walk(0, 0)

fun countPicks(prices: List<Int>, goal: Int): Int {
    fun walk(i: Int, total: Int): Int {
        if (total == goal) return 1 // more items only overshoot
        if (total > goal || i == prices.size) return 0
        return walk(i + 1, total + prices[i]) + walk(i + 1, total)
    }
    return walk(0, 0)
}

Common mistakes

• Counting the same selection twice by continuing after the goal is hit with skips.
• Pruning with negative prices, which can bring the total back down.

Draw the first three levels of the decision tree; it explains both the cost and the prune.

Follow-up questions

Think of your answer first, then open the hint.

1. When is DP better?

   Show hint

   When the goal is small enough for a table: O(n · goal) instead of exponential.

2. How do you list the selections instead of counting?

   Show hint

   Keep a path list, record a copy at each hit, and undo after each take.