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[0] = 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, naturallytable[0]=1

iteration for n = 1
 loop from 1 > 10 and sum
i + (i1)
 table[1] = table[1]+table[0] = 1
 table[2] = table[2]+table[1] = 1 and so on...
 table[10] = table[10]+table[9] = 1
 loop from 1 > 10 and sum

iteration for n = 2
 loop from 2 > 10 and sum
i + (i2)
 table[2] = table[2]+table[0] = 1+1 = 2
 table[3] = table[3]+table[1] = 1+1 = 2
 table[4] = table[4]+table[2] = 1+2 = 3, 3
 table[6] = table[6]+table[4] = 1+3 = 4, 4
 table[8] = table[8]+table[6] = 1+4 = 5, 5
 table[10] = table[10]+table[8] = 1+5 = 6
 loop from 2 > 10 and sum

iteration for n = 3
 loop from 3 > 10 and sum
i + (i3)
 table[3] = table[3]+table[0] = 2+1 = 3
 table[4] = table[4]+table[1] = 3+1 = 4
 table[7] = table[7]+table[4] = 4+4 = 8
 table[10] = table[10]+table[7] = 6+8 = 14
 loop from 3 > 10 and sum
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]
Additional Info
of course, another variant of the same problem is Given possible scores a batsman can score in one ball is {1, 2, 3}, how many ways can he score X runs in B balls  that is a tough one to explain!
but here's the solution nonetheless!
GeeksForGeeks
Top comments (0)