Algorithms and Data Structures

# 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. 1 + 1 + 2
1. 1 + 2 + 1
1. 2 + 1 + 1
1. 1 + 3
1. 3 + 1
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 =  * (N + 1)          # d[i] = all the combinations that sum up to `i`
d = 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` 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`) with let’s say 5 different ways and we know that we were able to obtain the number 8 (`d`) 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`) 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`
1. `d = [1, 0, 0, 0, 0]` → 1 way to obtain 0 and the rest are 0s
1. ```i = 1 ```num = 1 ⇒ d += d ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0
1. ```i = 2 ```num = 1 ⇒ d += d ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d += d ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0
1. ```i = 3 ```num = 1 ⇒ d += d ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d += d ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d += d ⇒ d = [1, 1, 2, 4, 0]
1. ```i = 4 ```num = 1 ⇒ d += d ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d += d ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d += d ⇒ d = [1, 1, 2, 4, 7]
1. `print(d)` → 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

1. 2 → 1 + 1, 2
1. 3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3

#### Constraints

Time limit: 0.5 seconds

Memory limit: 512 MB

Output limit: 1 MB