Code Logo

River Token Ways

Published at05 Jan 2026
Created by
Hard 18 views
Like5

You are given token values and a target total. The task is to count how many different combinations of tokens can add up to that target.

Order does not matter here. For example, using 2 + 1 + 1 + 1 is the same combination as 1 + 2 + 1 + 1. What matters is which token values are used and how many times.

For example, if tokens = [1,2,5] and target = 5, the answer is 4. The valid combinations are 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1. If tokens = [2] and target = 3, the answer is 0 because 2s alone can never make 3.

So the task is to count all unordered ways to reach the target using the available token values.

Example Input & Output

Example 1
Input
tokens = [1,2,5], target = 5
Output
4
Explanation

Four multisets reach the total: 5; 2+2+1; 2+1+1+1; and five copies of 1.

Example 2
Input
tokens = [2], target = 3
Output
0
Explanation

No combination of value 2 tokens can reach 3.

Example 3
Input
tokens = [10], target = 0
Output
1
Explanation

Choosing nothing is the single combination that meets the zero target.

Algorithm Flow

Recommendation Algorithm Flow for River Token Ways
Recommendation Algorithm Flow for River Token Ways

Solution Approach

This is the classic coin change combinations DP. Let dp[x] mean the number of ways to make total x.

We start with:

dp[0] = 1

That means there is one way to make total 0: choose nothing.

Then we process token values one by one. For each token, we update all reachable totals from that token value up to the target:

for (const token of tokens) {
  for (let x = token; x <= target; x++) {
    dp[x] += dp[x - token];
  }
}

Using the token loop on the outside is what avoids counting different orders as separate answers.

After the DP is filled, dp[target] is the number of valid combinations.

Best Answers

java
class Solution {
    public int count_token_combinations(int n, int[] tokens) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int t : tokens) {
            for (int i = t; i <= n; i++) {
                dp[i] += dp[i - t];
            }
        }
        return dp[n];
    }
}