3183. The Number of Ways to Make the Sum

Consider using dynamic programming.

Define dp[i][x] as the number of ways to make the sum x using only the first i coins; and define coin[i] as the value of coin i.

We can calculate dp[i][x] as the sum of dp[i - 1][x] and dp[i][x - coin[i]].

Remember that 4 can at most be multiplied twice, so we calculate the dp for our infinite coins and then manually handle the existence of 4.