00:00:00

Description

Editorial

Denomination Combination Count

MEDIUM20 pts

You are given an integer array denominations representing currency units of distinct face values, and an integer targetValue representing a total monetary amount you wish to assemble.

Your task is to determine how many unique ways you can combine these currency units to reach exactly the target amount. Each denomination can be used an unlimited number of times in any combination.

Key Characteristics:

Two combinations are considered different only if they contain different quantities of at least one denomination
The order in which denominations are selected does not create a new combination (i.e., selecting [1, 2] is the same as [2, 1])
If it is impossible to reach the exact target value using any combination of the available denominations, return 0
If the target value is 0, there is exactly one way to achieve it: by selecting no denominations at all

The result is guaranteed to fit within a signed 32-bit integer.

Example

Input

targetValue = 5
denominations = [1,2,5]

Output

4

Explanation

There are four distinct ways to assemble the value 5: • 5 = 5 (using one 5-unit) • 5 = 2 + 2 + 1 (using two 2-units and one 1-unit) • 5 = 2 + 1 + 1 + 1 (using one 2-unit and three 1-units) • 5 = 1 + 1 + 1 + 1 + 1 (using five 1-units)

Example

Input

targetValue = 3
denominations = [2]

Output

0

Explanation

The only available denomination is 2. Since 3 is odd and we can only add multiples of 2, it is impossible to reach exactly 3. Therefore, there are zero valid combinations.

Example

Input

targetValue = 10
denominations = [10]

Output

1

Explanation

With only a 10-unit denomination available, the only way to reach exactly 10 is to use one 10-unit. Hence, there is exactly one valid combination.

Accepted0/0·0% Acceptance

Constraints

1 ≤ denominations.length ≤ 300
1 ≤ denominations[i] ≤ 5000
All values in denominations are unique
0 ≤ targetValue ≤ 5000

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

coins =

[1,2,5]

amount =

Loading problem...

101

00:00:00

Description

Editorial

Denomination Combination Count

MEDIUM20 pts

You are given an integer array denominations representing currency units of distinct face values, and an integer targetValue representing a total monetary amount you wish to assemble.

Key Characteristics:

Two combinations are considered different only if they contain different quantities of at least one denomination
The order in which denominations are selected does not create a new combination (i.e., selecting [1, 2] is the same as [2, 1])
If it is impossible to reach the exact target value using any combination of the available denominations, return 0
If the target value is 0, there is exactly one way to achieve it: by selecting no denominations at all

The result is guaranteed to fit within a signed 32-bit integer.

Example

Input

targetValue = 5
denominations = [1,2,5]

Output

4

Explanation

Example

Input

targetValue = 3
denominations = [2]

Output

0

Explanation

The only available denomination is 2. Since 3 is odd and we can only add multiples of 2, it is impossible to reach exactly 3. Therefore, there are zero valid combinations.

Example

Input

targetValue = 10
denominations = [10]

Output

1

Explanation

With only a 10-unit denomination available, the only way to reach exactly 10 is to use one 10-unit. Hence, there is exactly one valid combination.

Accepted0/0·0% Acceptance

Constraints

1 ≤ denominations.length ≤ 300
1 ≤ denominations[i] ≤ 5000
All values in denominations are unique
0 ≤ targetValue ≤ 5000

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

coins =

[1,2,5]

amount =

Denomination Combination Count

Hints

Denomination Combination Count

Hints