# Combination Sum

Given the target value

`N`

and an array of allowed positive numbers, you are asked to count the ways to write `N`

as the sum of those numbers.So, if the allowed values are for instance

`[1, 2, 3]`

, and the number `N`

is 4, we can sum those numbers up in 7 different ways:## All the 7 ways to sum up 1, 2, 3 to obtain 4

- 1 + 1 + 1 + 1

- 1 + 1 + 2

- 1 + 2 + 1

- 2 + 1 + 1

- 1 + 3

- 3 + 1

- 2 + 2

This is a classic dynamic programming problem, which can be solved by keeping a state

`d[sum]`

which represents all the possible ways to obtain the `sum`

by combining the allowed numbers:```
N = ...
nums = [...]
d = [0] * (N + 1) # d[i] = all the combinations that sum up to `i`
d[0] = 1 # There is 1 way to get a 0 - not to take any numbers
for i in range(1, N + 1): # Try to obtain all the numbers sequentially 1...N
for num in nums: # Try to get `d[i]` with the help of `num`
if i - num >= 0: # If it's possible to obtain `i` from `num`
d[i] += d[i - num]
print(d[N])
```

So, our state

`d[i]`

is the number of ways we can obtain `i`

using the allowed numbers `nums`

. We initialize everything with 0 except `d[0]`

which we set to 1 as we can obtain 0 in only 1 way - by not using any of the allowed numbers. For all the other numbers, we look at all the possible ways we can obtain the numbers using `nums`

. If we can obtain the number 11 (

`d[11]`

) with letβs say 5 different ways and we know that we were able to obtain the number 8 (`d[8]`

) with 3 different ways, then in case there is 3 in the `nums`

array, we can obtain the number 11 with all the ways weβve found so far + all the ways we could obtain 8 (`d[8]`

) and then put the number 3 next to it.Letβs simulate the algorithm on the sample input:

`nums = [1, 2, 3]`

and `N = 4`

`d = [1, 0, 0, 0, 0]`

β 1 way to obtain 0 and the rest are 0s

`i = 1`

num = 1 β d[1] += d[0] β d = [1, 1, 0, 0, 0] num = 2 β i - num < 0 num = 3 β i - num < 0

`i = 2`

num = 1 β d[2] += d[1] β d = [1, 1, 1, 0, 0] num = 2 β d[2] += d[0] β d = [1, 1, 2, 0, 0] num = 3 β i - num < 0

`i = 3`

num = 1 β d[3] += d[2] β d = [1, 1, 2, 2, 0] num = 2 β d[3] += d[1] β d = [1, 1, 2, 3, 0] num = 3 β d[3] += d[0] β d = [1, 1, 2, 4, 0]

`i = 4`

num = 1 β d[4] += d[3] β d = [1, 1, 2, 4, 4] num = 2 β d[4] += d[2] β d = [1, 1, 2, 4, 6] num = 3 β d[4] += d[1] β d = [1, 1, 2, 4, 7]

`print(d[4])`

β prints 7

Β

Challenge - Dice Combinations

If you throw a die, it produces a number from 1 to 6. You are asked to compute the number of ways to obtain the number

`n`

by summing up together dice rolls. Input

The input contains a single integer

`n`

(1 β€ n β€ ). Output

The program should print the number of ways you can throw a die to obtain the number

`n`

as a sum of those throws. As the answer can get very large, you are asked to print it modulo . Examples

Input | Output |

2 | 2 |

3 | 4 |

Explanation

- 2 β 1 + 1, 2

- 3 β 1 + 1 + 1, 1 + 2, 2 + 1, 3

Β

#### Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB