Code Logo

Festival Glow Step Combinations

Published at05 Jan 2026
Created by
Hard 1 views
Like24

You want to reach exactly n using the allowed step sizes in steps. The answer is the number of different combinations that work.

The important detail is that order does not create a new answer here. The problem treats step sequences in nondecreasing order, so [1,2,1] is not counted separately from [1,1,2]. You only care about the combination itself.

For example, if n = 4 and steps = [1,2], the valid combinations are [1,1,1,1], [1,1,2], and [2,2], so the answer is 3. If n = 5 and steps = [2], the answer is 0 because no number of 2-step moves can add up to 5.

So the task is to count how many unordered step combinations sum to exactly n.

Example Input & Output

Example 1
Input
n = 4, steps = [1,2]
Output
3
Explanation

Valid sequences are [1,1,1,1], [1,1,2], and [2,2].

Example 2
Input
n = 5, steps = [2]
Output
0
Explanation

No combination of nondecreasing steps sums to 5.

Example 3
Input
n = 3, steps = [1,3]
Output
2
Explanation

Sequences [1,1,1] and [3] satisfy the nondecreasing rule.

Algorithm Flow

Recommendation Algorithm Flow for Festival Glow Step Combinations
Recommendation Algorithm Flow for Festival Glow Step Combinations

Solution Approach

This is the same dynamic programming pattern as coin change combinations. Each allowed step size can be used multiple times, but we want combinations, not permutations.

A simple 1D DP works well:

dp[0] = 1

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

Then for each allowed step size, we update totals from that step up to n:

for (const step of steps) {
  for (let total = step; total <= n; total++) {
    dp[total] += dp[total - step];
  }
}

Looping through step sizes first is what avoids double-counting different orders of the same combination.

At the end, dp[n] is the number of valid step combinations. This runs in O(n * m) time, where m is the number of allowed step sizes.

Best Answers

java

import java.util.*;
class Solution {
    public int festival_glow_step_combinations(Object n, Object steps) {
        int target = (int) n;
        int[] s_arr = (int[]) steps;
        int MOD = 1000000007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        Arrays.sort(s_arr);
        for (int s : s_arr) {
            for (int i = s; i <= target; i++) {
                dp[i] = (dp[i] + dp[i - s]) % MOD;
            }
        }
        return dp[target];
    }
}