Recipe Portion Counter

Minimum count of array values with repetition summing to a target

MediumDynamic ProgrammingUnbounded Knapsack

A recipe app stores several portion presets for a dish. Each preset produces a fixed positive number of serving units, listed in units.

You may use any preset any number of times. Every use counts as one portion, even when two presets produce the same number of serving units. Portions cannot be split, and their serving units add together.

Return the minimum number of portions needed to produce exactly target serving units. Return -1 if this is impossible. For a target of zero, return 0.

Examples

Example 1

Input: units = [3,4,7], target = 8
Output: 2

Two uses of the four-unit preset reach the target. No single preset produces the target.

Example 2

Input: units = [4,6], target = 9
Output: -1

Every available preset produces an even number of units, so the odd target cannot be reached.

Example 3

Input: units = [1,3,4], target = 6
Output: 2

Using two three-unit portions requires fewer portions than using one four-unit portion and two one-unit portions.

Constraints

  • 1 <= units.length <= 200
  • 1 <= units[i] <= 20000
  • 0 <= target <= 20000
  • Preset sizes may repeat.
  • Each preset may be used any number of times.

The intended solution takes O(target * d) time and O(target) space, where d is the number of distinct preset sizes no greater than the target.

Hints

Show hint 1

Let dp[a] represent the fewest portions needed to produce exactly a serving units.

Show hint 2

For each reachable smaller total, consider adding one preset. Initialize the zero total separately and keep impossible totals marked as unreachable.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you also return one optimal list of preset sizes, in nondecreasing order?
  • How would the recurrence change if each preset could be used only a specified number of times?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem