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

• iteration for n = 1

  • loop from 1 -> 10 and sum i + (i-1)
  • table[1] = table[1]+table[0] = 1
  • table[2] = table[2]+table[1] = 1 and so on...
  • table[10] = table[10]+table[9] = 1

• iteration for n = 2

  • loop from 2 -> 10 and sum i + (i-2)
  • 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

• iteration for n = 3

  • loop from 3 -> 10 and sum i + (i-3)
  • 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

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