FastPrep
Problem · Dynamic Programming

Count Ordered Size Sequences

Learn this problem
● MediumOptiver logoOptiverFULLTIMEOA

Problem statement

Given a positive target n and an array of distinct positive integers sizes, count the ordered sequences of values from sizes whose sum is exactly n.

Each size may be used any number of times. Two sequences are different when they differ at any position, so order matters.

Return the number of valid sequences.

Function

countOrderedSums(n: int, sizes: int[]) → long

Examples

Example 1

n = 3sizes = [1,2]return = 3

The valid ordered sequences are [1,1,1], [1,2], and [2,1].

Example 2

n = 4sizes = [1,3]return = 3

The sequences are [1,1,1,1], [1,3], and [3,1].

Constraints

  • 1 <= n <= 60
  • 1 <= sizes.length <= 60
  • 1 <= sizes[i] <= n
  • All values in sizes are distinct.
  • The answer fits in a signed 64-bit integer.

More Optiver problems

drafts saved locally
public long countOrderedSums(int n, int[] sizes) {
    // write your code here
}
n3
sizes[1,2]
expected3
checking account