Quick Overview

Count distinct ways to reach a target with unlimited coins, treating different orders of the same denominations as one combination.

Count Unordered Combinations of Unlimited Coins

Company: Worldquant

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Given an array `coins` of positive coin denominations and a nonnegative integer `target`, return the number of distinct combinations of coins whose total value is exactly `target`. You may use each denomination an unlimited number of times. The order of coins within a combination does not matter. For example, `[1, 2, 1]` and `[2, 1, 1]` represent the same combination. ### Function Contract Implement `count_coin_combinations(coins, target) -> int`. Return the exact combination count. Do not return the combinations themselves and do not apply a modulus. ### Constraints and Clarifications The following bounds and duplicate-denomination rule are explicit practice assumptions: - `0 <= len(coins) <= 100`. - Every denomination is an integer from `1` through `10000`. - Denominations are distinct, and the input order may be arbitrary. - `0 <= target <= 100`. - The count fits a signed 32-bit integer under these bounds. - There is one way to make a target of zero: choose no coins. - With no denominations, a positive target has zero combinations. ### Examples ```text coins = [1, 2, 3] target = 4 Output: 4 ``` The combinations are four `1` coins; two `1` coins and one `2`; two `2` coins; and one `1` plus one `3`. ```text coins = [2] target = 3 Output: 0 ``` ```hint Give every combination one counting order The same multiset of coins can be assembled in several sequences. Choose a state progression that counts the multiset once rather than once per sequence. ```

Overview: Count distinct ways to reach a target with unlimited coins, treating different orders of the same denominations as one combination.

Given an array `coins` of positive coin denominations and a nonnegative integer `target`, return the number of distinct combinations of coins whose total value is exactly `target`. You may use each denomination an unlimited number of times. The order of coins within a combination does not matter. For example, `[1, 2, 1]` and `[2, 1, 1]` represent the same combination and are counted once. Implement `count_coin_combinations(coins, target) -> int`. Return the exact combination count. Do not return the combinations themselves and do not apply a modulus. The denominations are distinct and may be supplied in arbitrary order; the answer does not depend on that order. There is one way to make a target of zero (choose no coins), and with no denominations at all a positive target has zero combinations. Under the stated bounds the answer always fits in a signed 32-bit integer, so `int` is sufficient in Java and C++. Example 1: coins = [1, 2, 3] target = 4 Output: 4 The combinations are four `1` coins; two `1` coins and one `2`; two `2` coins; and one `1` plus one `3`. Example 2: coins = [2] target = 3 Output: 0 No multiset of `2` coins sums to `3`.

Constraints

  • 0 <= len(coins) <= 100
  • Every denomination is an integer from 1 through 10000
  • Denominations are distinct, and the input order may be arbitrary
  • 0 <= target <= 100
  • The count fits a signed 32-bit integer under these bounds
  • There is one way to make a target of zero: choose no coins
  • With no denominations, a positive target has zero combinations
  • Each denomination may be used an unlimited number of times
  • Combinations are unordered: two selections using the same coins in a different order are the same combination

Examples

Input: ([], 0)

Expected Output: 1

Explanation: No denominations and a target of zero: the single combination is the empty selection, so the answer is 1.

Input: ([1, 2, 5], 0)

Expected Output: 1

Explanation: A target of zero is made exactly one way regardless of which denominations are available: choose no coins.

Hints

  1. The same multiset of coins can be assembled in several sequences. Choose a state progression that counts each multiset once rather than once per sequence.
  2. The statement already fixes the answer for a target of zero; make that the base case of whatever progression you build up from.
  3. A denomination larger than the target can never appear in any combination, so it cannot affect the answer.

Loading coding console...

Show the approach

Approach

Algorithm. Keep a one-dimensional table dp of length target + 1 and process the denominations one at a time in an outer loop, sweeping amounts upward in an inner loop: dp[amount] += dp[amount - coin].

Invariant. After the first k denominations have been processed, dp[a] equals the number of multisets drawn only from those k denominations whose values sum to a, for every a in 0..target. The base dp[0] = 1, dp[a > 0] = 0 is the k = 0 case: the empty selection is the one way to reach 0, and no positive amount is reachable with no denominations.

Correctness. Fix the k-th denomination c. Every multiset over the first k denominations summing to a either uses no copy of c (counted by the value dp[a] already held from step k - 1) or uses at least one copy, in which case removing exactly one c leaves a multiset over the first k denominations summing to a - c. Those two families are disjoint and exhaustive, so dp_k[a] = dp_{k-1}[a] + dp_k[a - c]. Sweeping amount upward means dp[amount - coin] has already been updated for the current denomination, which is exactly dp_k[a - c]; the same denomination is therefore allowed unlimited times, while the outer loop visits each denomination once so a multiset is generated in exactly one order. This is what makes the count order-insensitive: reversing the loop nesting (amounts outside, denominations inside) would count ordered sequences instead, reporting 7 rather than 4 for coins = [1, 2, 3], target = 4.

Edge cases. target = 0 makes dp a single cell holding 1, and since every denomination is at least 1 it is skipped by the coin > target guard, so the answer is 1 for any coin list, including the empty one. An empty coins array leaves dp untouched, so a positive target returns 0. The coin > target guard also covers denominations up to 10000 that can never be used and keeps the inner index nonnegative. The input order of coins is irrelevant because the recurrence is applied once per denomination and addition is commutative. With target <= 100 and denominations 1..100 the largest possible answer is p(100) = 190569292, which fits in a signed 32-bit integer, so int (Java, C++) and a JavaScript number are exact.

Time complexity:
O(n * target), where n is the number of denominations
Space complexity:
O(target)