Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Consider using dynamic programming.
Define <code>dp[i][x]</code> as the number of ways to make the sum <code>x</code> using only the first <code>i</code> coins; and define <code>coin[i]</code> as the value of coin <code>i</code>.
We can calculate <code>dp[i][x]</code> as the sum of <code>dp[i - 1][x]</code> and <code>dp[i][x - coin[i]]</code>.
Remember that 4 can at most be multiplied twice, so we calculate the <code>dp</code> for our infinite coins and then manually handle the existence of 4.