FastPrepCount Unordered Coin Combinations

Count Unordered Coin Combinations

WorldQuant logoWorldQuant● MediumNEW GRADOA
Learn

Problem statement

Given an array of distinct positive integers coins, where each value is a coin denomination, and a nonnegative integer target, return the number of distinct combinations that sum to target.

You may use each denomination any number of times. The order of chosen coins does not create a different combination. For example, [1, 2, 1] and [2, 1, 1] represent the same combination.

When target is 0, there is exactly one combination: choose no coins.

Function

countCombinations(coins: int[], target: int) → int

Examples

Example 1

coins = [1,2,3]target = 4return = 4

The four combinations are [1, 1, 1, 1], [1, 1, 2], [2, 2], and [1, 3].

Example 2

coins = [2]target = 3return = 0

No number of coins with denomination 2 sums to 3.

Example 3

coins = [2,5]target = 0return = 1

The empty selection is the only combination whose sum is 0.

Constraints

  • 1 ≤ coins.length ≤ 300.
  • 1 ≤ coins[i] ≤ 5000.
  • All values in coins are distinct.
  • 0 ≤ target ≤ 5000.
  • The answer fits in a signed 32-bit integer.
See WorldQuant hiring insights
public int countCombinations(int[] coins, int target) {
    // write your code here
}
coins[1,2,3]
target4
expected4
Checking account…