# Problem Statement

The purpose of this blog is to explain the problem of achieving a final score, given the set of input balls. Let's understand a pool game first. A pool table consists of six pockets and balls numbered from 1 to 15. A player scores when he pockets a ball (taking the ball numbered two gives the equivalent two).

Let's take an example of a custom pool game with valid balls, which is the selection of only a few numbered balls from the set. We have to find the number of ways a player can reach a final score using valid balls.

Let's say that the user has selected three balls (2, 4 and 6), and played the pool table, and his final score is 6. There are four number of ways the player can score six by pocketing [{2,2,2}, {2,4}, {4,2}, {6}].

We have to define a method that accepts valid and final input and return number of ways to reach a score.

# Explanation

We have an input array named *valid* to store the chosen balls and a number *final* defining the final score of the player.

We define an array named *ways* to store the number of ways to reach an element denoted by index. Example, *ways[i]* means the number of ways to reach i.

Let's say that the user has selected three balls (2, 4 and 6) and achieved a final score of 6.

Given,

```
valid = [2, 4, 6]
final = 6
ways = [0, 0, 0, 0, 0, 0]
```

The idea is to iterate over each score and try to find how any valid score impacts on the number of ways to achieve this score.

**Score 1**

There are no valid scores that impacts the score 1

Set the number of ways to reach 1, denoted by *ways[1]*

```
ways[1] = 0
```

**Score 2**

There is one valid scores that impacts the score 2 - [2]

Set the number of ways to reach 2, denoted by *ways[2]*

```
ways[2] = ways[2] + 1
ways[2] = 1
```

**Score 3**

There is one valid scores that impacts the score 3 - [2]

We know that we can find ways to reach a final score of 3, using ways to reach a final score of 1

Set the number of ways to reach 3, denoted by *ways[3]*

```
ways[3] = ways[3] + ways[1]
ways[3] = 0
```

**Score 4**

There are two valid scores that impacts the score 4 - [2, 4]

We know that we can find ways to reach a final score of 4, using ways to reach a final score of 2 and 4

Set the number of ways to reach 4, denoted by *ways[4]*

```
ways[4] = ways[4] + 1
ways[4] = ways[4] + ways[2]
ways[4] = 2
```

**Score 5**

There are two valid scores that impacts the score 5 - [2, 4]

We know that we can find ways to reach a final score of 5, using ways to reach a final score of 1 and 3

Set the number of ways to reach 5, denoted by *ways[5]*

```
ways[5] = ways[5] + ways[3] + ways[1]
ways[5] = 0
```

**Score 6**

There are three valid scores that impacts the score 6 - [2, 4, 6]

We know that we can find ways to reach a final score of 6, using ways to reach a final score of 2, 4 and 6

Set the number of ways to reach 6, denoted by *ways[6]*

```
ways[6] = ways[6] + 1
ways[6] = ways[6] + ways[4] + ways[2]
ways[6] = 4
```

similarly for demonstration of scores greater than 6

```
ways[8] = ways[8] + ways[6] + ways[4] + ways[2]
ways[8] = 7
```

Final result in the *ways* array

```
ways = [0, 1, 0, 2, 0, 4]
```

We can get the number of ways to reach six, as three (using *ways[6]*).

# Code

```
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
// Input
// Valid Points - 2, 4, 6
// Final Point - 6
// Output - Ways to achieve final point using valid points with all the combinations
// 6 can be achieved using 4 ways - [2,2,2], [2,4], [4,2] and [6]
// 8 can be made using 7 ways - [2,2,2,2], [2,2,4], [2,4,2], [4,2,2], [2,6], [6,2] and [8]
Console.WriteLine(NumberOfWaysWithCombination(new int[]{2, 4, 6}, 6));
Console.WriteLine(NumberOfWaysWithCombination(new int[]{2, 4, 6}, 8));
}
public static int NumberOfWaysWithCombination(int[] valid, int final) {
if(valid == null || valid.Length == 0 || final <= 0) {
return 0;
}
var ways = new int[final + 1];
// Base condition to denote a number can be formed by it's own
// e.g. 2 can be formed if 2 is a valid score and so on
ways[0] = 1;
// The idea is to perform additive operation for all the valid scores
// until we reach the final
for(var i = 1; i <= final; i++) {
// Perform the addition for combination of ways to reach final score
foreach(var input in valid.Where(item => i >= item)) {
ways[i] += ways[i-input];
}
}
return ways[final];
}
}
}
```