Skip to the code
cf.
+25 XP

#514 Count Cart Selections Hitting a Total

medium

A promotion gives a prize to any order that costs exactly target. The store has items with whole-number prices, and each item can be in the cart at most once. Items are different even when their prices are equal.

Write countSelections(prices, target) that returns how many different sets of items cost exactly target, modulo 1000000007.

Example 1

Input: prices = [1,2,3,4], target = 5
Output: 2

Items priced 1 + 4, or 2 + 3.

Example 2

Input: prices = [2,2,2], target = 4
Output: 3

Any two of the three items priced 2: there are 3 pairs.

Constraints

  • 1 <= prices.length <= 200
  • 1 <= prices[i] <= 1000
  • 1 <= target <= 5000
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).