Find all possible ways to express a given number, n as a sum of 1,2,3 assuming that we can reuse 1 or 2 or 3 many times and we may or may need 1 or 2 or 3 in each result.
Example
n=3
Ans: 4 since there are 4 ways to express 4 as a sum of 1,2,3
{1,1,1}, {1,2}, {2,1} , {3}
Solutions:
This problem is can be solved by solving the sub problems (dynamic programing) using recursion.
Basically, we have the option to include or not to include {1,2,3} in each result
Therefore, when we don't need 1 in the result, we have to remove it also from the given sum (eg 3-1 when n=3 => sum becomes 2)
Therefore the solution is adding each sub solution by including and excluding {1,2,3} from the list.
We use memorization to store values that we have already computed in memory so that we don't have to calculate them again.
public int Helper(int[] memo, int n) {
if (n == 0)
return 1;
if (n == 1)
return 1;
if (n == 2)
return 1;
if (n == 3)
return 2;
if (memo[n] == 0) {
int result1 = Helper(memo, n - 1);
int result2 = Helper(memo, n - 2);
int result3 = Helper(memo, n - 3);
memo[n] = result1 + result2 + result3;
}
return memo[n];
}