## DEV Community # Misc: Possible Ways to Add

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

## Problem

A very interesting and fairly easy question which I found during one interview was:

A batsman can score either {1,2,3} runs in a ball. Find the number of ways he can score "X".

Other variants - Given possible coins 2, 3, 5 - how many ways can result in a sum of 43

If you got stuck thinking or applying permutations and then visualizing it in code - just look at this simple code

## Solution

``````    static int possibleWaysToReachScore(List<Integer> runs, int x) {

// table[i] will store count of solutions for value i.
int[] table = new int[x + 1];

// Initialize all table values as 0
Arrays.fill(table, 0);

// Base case (If given value is 0)
table = 1;

// One by one consider given runs
// and update the table[]
// values after the index greater
// than or equal to the value of
// the picked move
runs.forEach(
n -> IntStream.rangeClosed(n, x)
.forEach(i -> table[i] += table[i - n])
);

return table[x];
}
``````

## Explanation:

• given we have 1,2,3 and we want say 10 runs, we start with a dp array which will store all possible ways to get to the index (which represents the runs).
so, naturally `table=1`

• iteration for n = 1

• loop from 1 -> 10 and sum `i + (i-1)`
• table = table+table = 1
• table = table+table = 1 and so on...
• table = table+table = 1
• iteration for n = 2

• loop from 2 -> 10 and sum `i + (i-2)`
• table = table+table = 1+1 = 2
• table = table+table = 1+1 = 2
• table = table+table = 1+2 = 3, 3
• table = table+table = 1+3 = 4, 4
• table = table+table = 1+4 = 5, 5
• table = table+table = 1+5 = 6
• iteration for n = 3

• loop from 3 -> 10 and sum `i + (i-3)`
• table = table+table = 2+1 = 3
• table = table+table = 3+1 = 4
• table = table+table = 4+4 = 8
• table = table+table = 6+8 = 14

then we loop over the range n (the current score possible till required score)

in the end we will have a dp containing all ways to reach any number till X
`[(0=1), (1=1), (2=2), 3, 4, 5, (6=7), 8, 10, (9=12), 14]`