Introduction

When people ask for the number of combinations that form 100, the first thing to clarify is the rule set. The answer depends on which numbers are allowed and whether different orders count separately or whether 25 + 75 and 75 + 25 should be treated as the same combination.

Model it as a combination-counting problem

The most common version is the coin-change style problem:

• You have a list of allowed numbers.
• You want the total to be 100.
• Order does not matter.
• Each allowed number may be used zero or more times.

That means you are counting combinations, not permutations. A dynamic programming approach is a good fit because many smaller totals get reused while building larger totals.

For example, if the allowed numbers are [1, 5, 10, 25], you can count how many combinations sum to 100 without generating every sequence explicitly.

Use dynamic programming for an efficient solution

The key idea is to let dp[s] store the number of ways to make sum s. Start with one way to make zero, which is "choose nothing," then update the table for each allowed number.

1def count_combinations(target: int, numbers: list[int]) -> int:
2    dp = [0] * (target + 1)
3    dp[0] = 1
4
5    for number in numbers:
6        for total in range(number, target + 1):
7            dp[total] += dp[total - number]
8
9    return dp[target]
10
11
12print(count_combinations(100, [1, 5, 10, 25]))

Why does this work? When you process a number such as 10, every way to build total - 10 can become a way to build total by adding one more 10. Because you loop over the allowed numbers on the outside, you count each combination once instead of recounting the same values in different orders.

This runs in O(target * len(numbers)) time and O(target) space, which is very reasonable for a target of 100.

A recursive version with memoization

If you want something closer to the mathematical definition, recursion is also fine as long as you memoize repeated subproblems.

1from functools import lru_cache
2
3
4def count_combinations_recursive(target: int, numbers: list[int]) -> int:
5    numbers = tuple(sorted(numbers))
6
7    @lru_cache(maxsize=None)
8    def solve(remaining: int, index: int) -> int:
9        if remaining == 0:
10            return 1
11        if remaining < 0 or index == len(numbers):
12            return 0
13
14        use_current = solve(remaining - numbers[index], index)
15        skip_current = solve(remaining, index + 1)
16        return use_current + skip_current
17
18    return solve(target, 0)
19
20
21print(count_combinations_recursive(100, [1, 5, 10, 25]))

This version makes the choice structure explicit:

• Use the current number again.
• Skip the current number and move to the next choice.

Memoization prevents the same state from being solved again and again.

Special case: all positive integers that sum to 100

If the allowed numbers are all positive integers from 1 through 100, you are computing the number of integer partitions of 100. The dynamic programming function still works:

numbers = list(range(1, 101))
print(count_combinations(100, numbers))

That gives the number of unordered partitions of 100. If instead order matters, you need a different recurrence because 1 + 99 and 99 + 1 would become distinct results.

For the order-sensitive version, the loop order changes:

1def count_ordered_ways(target: int, numbers: list[int]) -> int:
2    dp = [0] * (target + 1)
3    dp[0] = 1
4
5    for total in range(1, target + 1):
6        for number in numbers:
7            if total >= number:
8                dp[total] += dp[total - number]
9
10    return dp[target]

That is a different question, so it is important not to mix the two interpretations.

Why generation is often worse than counting

A tempting approach is to generate every combination and then count them. That works for tiny problems, but it scales much worse because the number of valid results can become very large.

If all you need is the count, dynamic programming is usually the better tool. It gives the answer directly without storing every actual combination in memory.

Common Pitfalls

The biggest mistake is failing to define whether order matters. Many incorrect solutions are actually solving the permutation problem instead of the combination problem.

Another common issue is not specifying the allowed numbers. There is no single universal answer to "form 100" unless the candidate set is known.

People also write recursive solutions without memoization, which can become extremely slow because the same subproblems repeat many times.

Finally, be careful with loop order in the dynamic programming version. Swapping the loops changes the meaning of the algorithm and can turn a combination counter into an order-sensitive counter.

Summary

• The correct algorithm depends on the allowed numbers and whether order matters.
• For unordered combinations, dynamic programming is the most practical approach.
• A memoized recursive solution works too and mirrors the mathematical structure nicely.
• If the allowed set is 1..100, the problem becomes the partition-counting problem.
• Loop order in dynamic programming is crucial because it changes what gets counted.