Mixing
Coin change with fixed denominations with duplicate values
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Suppose I have $1, 1 2, 2, 2 5 10$ coins.
How many ways I can get 15 by adding coins?
If I use DP then it counts 7, because $1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10$ and $10 + 5$. But actual result is $1+2+2+10$ and $10 + 5$. How do I solve efficiently?
Now I able to figure out the solution. I have to find integral solutions of equation $x+2y+5z+10m=15$ with constraints $x <= 2$, $y <= 3$, $z <= 1$ and $m <= 1$. Now how to do that?
combinatorics dynamic-programming
asked 2 days ago
Debasis Jana
63
add a comment |Â
up vote
1
down vote
favorite
Suppose I have $1, 1 2, 2, 2 5 10$ coins.
How many ways I can get 15 by adding coins?
If I use DP then it counts 7, because $1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10$ and $10 + 5$. But actual result is $1+2+2+10$ and $10 + 5$. How do I solve efficiently?
Now I able to figure out the solution. I have to find integral solutions of equation $x+2y+5z+10m=15$ with constraints $x <= 2$, $y <= 3$, $z <= 1$ and $m <= 1$. Now how to do that?
combinatorics dynamic-programming
asked 2 days ago
Debasis Jana
63
1
dynamic programming geeksforgeeks.org/dynamic-programming-subset-sum-problem
– Debasis Jana
2 days ago
Your DP answer repeats combinations, suggesting that you are thinking of the coins with the same value as different from each other. The "actual result" suggests they are the same. And you're missing combinations with $(1,1)$ replacing a $(2)$. Please edit the question to clarify. That said, I suspect there is no good algorithm to count what you want.
– Ethan Bolker
2 days ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Suppose I have $1, 1 2, 2, 2 5 10$ coins.
How many ways I can get 15 by adding coins?
If I use DP then it counts 7, because $1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10$ and $10 + 5$. But actual result is $1+2+2+10$ and $10 + 5$. How do I solve efficiently?
Now I able to figure out the solution. I have to find integral solutions of equation $x+2y+5z+10m=15$ with constraints $x <= 2$, $y <= 3$, $z <= 1$ and $m <= 1$. Now how to do that?
combinatorics dynamic-programming
asked 2 days ago
Debasis Jana
63
Suppose I have $1, 1 2, 2, 2 5 10$ coins.
How many ways I can get 15 by adding coins?
If I use DP then it counts 7, because $1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10 1+2+2+10$ and $10 + 5$. But actual result is $1+2+2+10$ and $10 + 5$. How do I solve efficiently?
Now I able to figure out the solution. I have to find integral solutions of equation $x+2y+5z+10m=15$ with constraints $x <= 2$, $y <= 3$, $z <= 1$ and $m <= 1$. Now how to do that?
combinatorics dynamic-programming
asked 2 days ago
Debasis Jana
63
edited 2 days ago
asked 2 days ago
Debasis Jana
63
asked 2 days ago
Debasis Jana
63
asked 2 days ago
Debasis Jana
63
63
1
dynamic programming geeksforgeeks.org/dynamic-programming-subset-sum-problem
– Debasis Jana
2 days ago
Your DP answer repeats combinations, suggesting that you are thinking of the coins with the same value as different from each other. The "actual result" suggests they are the same. And you're missing combinations with $(1,1)$ replacing a $(2)$. Please edit the question to clarify. That said, I suspect there is no good algorithm to count what you want.
– Ethan Bolker
2 days ago
add a comment |Â
1
dynamic programming geeksforgeeks.org/dynamic-programming-subset-sum-problem
– Debasis Jana
2 days ago
Your DP answer repeats combinations, suggesting that you are thinking of the coins with the same value as different from each other. The "actual result" suggests they are the same. And you're missing combinations with $(1,1)$ replacing a $(2)$. Please edit the question to clarify. That said, I suspect there is no good algorithm to count what you want.
– Ethan Bolker
2 days ago
1
1
dynamic programming geeksforgeeks.org/dynamic-programming-subset-sum-problem
– Debasis Jana
2 days ago
dynamic programming geeksforgeeks.org/dynamic-programming-subset-sum-problem
– Debasis Jana
2 days ago
Your DP answer repeats combinations, suggesting that you are thinking of the coins with the same value as different from each other. The "actual result" suggests they are the same. And you're missing combinations with $(1,1)$ replacing a $(2)$. Please edit the question to clarify. That said, I suspect there is no good algorithm to count what you want.
– Ethan Bolker
2 days ago
Your DP answer repeats combinations, suggesting that you are thinking of the coins with the same value as different from each other. The "actual result" suggests they are the same. And you're missing combinations with $(1,1)$ replacing a $(2)$. Please edit the question to clarify. That said, I suspect there is no good algorithm to count what you want.
– Ethan Bolker
2 days ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
The generating function for the number of solutions in integers to
$$x_1 + 2x_2 + 5 x_3 + 10 x_4 = r$$
subject to $0 le x_1 le 2$, $0 le x_2 le 3$, $0 le x_3 le 1$ and $0 le x_4 le 1$ is
$$f(x) = (1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)$$
The answer to your problem is the coefficient of $x^15$ when this polynomial is expanded, which is $2$. I used a computer algebra system for the expansion. Expanding the polynomial by hand is possible, but tedious unless you can find a shortcut.
Another approach is to observe that using only coins of denomination 1, 2, or 5, the largest amount you can make is 13, so you must use one coin of denomination 10 if the total is to be 15. That leaves an amount of 5 to be made up from coins of denomination 1, 2, or 5. There aren't many cases to consider, and you can probably see that the only possibilities are 5 and 1+2+2.
answered 2 days ago
awkward
5,04611021
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
add a comment |Â
up vote
1
down vote
This is a supplement to the already given answer showing that calculating the coefficient is not that cumbersome. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial.
We obtain
beginalign*
colorblue[x^15]&colorblue(1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)\
&=[x^15](1+x^5+x^10+x^15)(1+x+x^2)(1+x^2+x^4+x^6)tag1\
&=left([x^15]+[x^10]+[x^5]+[x^0]right)(1+x+x^2)(1+x^2+x^4+x^6)tag2\
&=left([x^5]+[x^0]right)(colorblue1+x+x^2)(colorblue1+x^2+x^4+x^6)tag3\
&=1+[x^5](1+colorbluex+x^2)(1+x^2+colorbluex^4+x^6)tag4\
&=1+1tag5\
&,,colorblue=2
endalign*
Comment:
In (1) we multiply out the terms with the highest powers which is convenient as we will see in step (3).
In (2) we use the linearity of the coefficient of operator and apply the rule $[x^p-q]A(x)=[x^p]x^qA(x)$.
In (3) we can skip $[x^15]$ and $[x^10]$ since they do not contribute as the highest power of $x$ is $8$.
In (4) we select the coefficient of $x^0$.
In (5) we select the coefficient of $x^5$.
answered 2 days ago
Markus Scheuer
55.7k450135
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
1
Good point (+1). Thank you.
– awkward
yesterday
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The generating function for the number of solutions in integers to
$$x_1 + 2x_2 + 5 x_3 + 10 x_4 = r$$
subject to $0 le x_1 le 2$, $0 le x_2 le 3$, $0 le x_3 le 1$ and $0 le x_4 le 1$ is
$$f(x) = (1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)$$
The answer to your problem is the coefficient of $x^15$ when this polynomial is expanded, which is $2$. I used a computer algebra system for the expansion. Expanding the polynomial by hand is possible, but tedious unless you can find a shortcut.
Another approach is to observe that using only coins of denomination 1, 2, or 5, the largest amount you can make is 13, so you must use one coin of denomination 10 if the total is to be 15. That leaves an amount of 5 to be made up from coins of denomination 1, 2, or 5. There aren't many cases to consider, and you can probably see that the only possibilities are 5 and 1+2+2.
answered 2 days ago
awkward
5,04611021
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
add a comment |Â
up vote
1
down vote
The generating function for the number of solutions in integers to
$$x_1 + 2x_2 + 5 x_3 + 10 x_4 = r$$
subject to $0 le x_1 le 2$, $0 le x_2 le 3$, $0 le x_3 le 1$ and $0 le x_4 le 1$ is
$$f(x) = (1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)$$
The answer to your problem is the coefficient of $x^15$ when this polynomial is expanded, which is $2$. I used a computer algebra system for the expansion. Expanding the polynomial by hand is possible, but tedious unless you can find a shortcut.
Another approach is to observe that using only coins of denomination 1, 2, or 5, the largest amount you can make is 13, so you must use one coin of denomination 10 if the total is to be 15. That leaves an amount of 5 to be made up from coins of denomination 1, 2, or 5. There aren't many cases to consider, and you can probably see that the only possibilities are 5 and 1+2+2.
answered 2 days ago
awkward
5,04611021
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The generating function for the number of solutions in integers to
$$x_1 + 2x_2 + 5 x_3 + 10 x_4 = r$$
subject to $0 le x_1 le 2$, $0 le x_2 le 3$, $0 le x_3 le 1$ and $0 le x_4 le 1$ is
$$f(x) = (1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)$$
The answer to your problem is the coefficient of $x^15$ when this polynomial is expanded, which is $2$. I used a computer algebra system for the expansion. Expanding the polynomial by hand is possible, but tedious unless you can find a shortcut.
Another approach is to observe that using only coins of denomination 1, 2, or 5, the largest amount you can make is 13, so you must use one coin of denomination 10 if the total is to be 15. That leaves an amount of 5 to be made up from coins of denomination 1, 2, or 5. There aren't many cases to consider, and you can probably see that the only possibilities are 5 and 1+2+2.
answered 2 days ago
awkward
5,04611021
The generating function for the number of solutions in integers to
$$x_1 + 2x_2 + 5 x_3 + 10 x_4 = r$$
subject to $0 le x_1 le 2$, $0 le x_2 le 3$, $0 le x_3 le 1$ and $0 le x_4 le 1$ is
$$f(x) = (1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)$$
The answer to your problem is the coefficient of $x^15$ when this polynomial is expanded, which is $2$. I used a computer algebra system for the expansion. Expanding the polynomial by hand is possible, but tedious unless you can find a shortcut.
Another approach is to observe that using only coins of denomination 1, 2, or 5, the largest amount you can make is 13, so you must use one coin of denomination 10 if the total is to be 15. That leaves an amount of 5 to be made up from coins of denomination 1, 2, or 5. There aren't many cases to consider, and you can probably see that the only possibilities are 5 and 1+2+2.
answered 2 days ago
awkward
5,04611021
answered 2 days ago
awkward
5,04611021
answered 2 days ago
awkward
5,04611021
answered 2 days ago
awkward
5,04611021
5,04611021
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
add a comment |Â
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
Marcus Scheuer's solution shows that pencil and paper expansion of the generating function to find the coefficient of $x^15$ is not tedious, if approached correctly.
– awkward
yesterday
add a comment |Â
up vote
1
down vote
This is a supplement to the already given answer showing that calculating the coefficient is not that cumbersome. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial.
We obtain
beginalign*
colorblue[x^15]&colorblue(1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)\
&=[x^15](1+x^5+x^10+x^15)(1+x+x^2)(1+x^2+x^4+x^6)tag1\
&=left([x^15]+[x^10]+[x^5]+[x^0]right)(1+x+x^2)(1+x^2+x^4+x^6)tag2\
&=left([x^5]+[x^0]right)(colorblue1+x+x^2)(colorblue1+x^2+x^4+x^6)tag3\
&=1+[x^5](1+colorbluex+x^2)(1+x^2+colorbluex^4+x^6)tag4\
&=1+1tag5\
&,,colorblue=2
endalign*
Comment:
In (1) we multiply out the terms with the highest powers which is convenient as we will see in step (3).
In (2) we use the linearity of the coefficient of operator and apply the rule $[x^p-q]A(x)=[x^p]x^qA(x)$.
In (3) we can skip $[x^15]$ and $[x^10]$ since they do not contribute as the highest power of $x$ is $8$.
In (4) we select the coefficient of $x^0$.
In (5) we select the coefficient of $x^5$.
answered 2 days ago
Markus Scheuer
55.7k450135
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
1
Good point (+1). Thank you.
– awkward
yesterday
add a comment |Â
up vote
1
down vote
This is a supplement to the already given answer showing that calculating the coefficient is not that cumbersome. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial.
We obtain
beginalign*
colorblue[x^15]&colorblue(1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)\
&=[x^15](1+x^5+x^10+x^15)(1+x+x^2)(1+x^2+x^4+x^6)tag1\
&=left([x^15]+[x^10]+[x^5]+[x^0]right)(1+x+x^2)(1+x^2+x^4+x^6)tag2\
&=left([x^5]+[x^0]right)(colorblue1+x+x^2)(colorblue1+x^2+x^4+x^6)tag3\
&=1+[x^5](1+colorbluex+x^2)(1+x^2+colorbluex^4+x^6)tag4\
&=1+1tag5\
&,,colorblue=2
endalign*
Comment:
In (1) we multiply out the terms with the highest powers which is convenient as we will see in step (3).
In (2) we use the linearity of the coefficient of operator and apply the rule $[x^p-q]A(x)=[x^p]x^qA(x)$.
In (3) we can skip $[x^15]$ and $[x^10]$ since they do not contribute as the highest power of $x$ is $8$.
In (4) we select the coefficient of $x^0$.
In (5) we select the coefficient of $x^5$.
answered 2 days ago
Markus Scheuer
55.7k450135
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
1
Good point (+1). Thank you.
– awkward
yesterday
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This is a supplement to the already given answer showing that calculating the coefficient is not that cumbersome. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial.
We obtain
beginalign*
colorblue[x^15]&colorblue(1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)\
&=[x^15](1+x^5+x^10+x^15)(1+x+x^2)(1+x^2+x^4+x^6)tag1\
&=left([x^15]+[x^10]+[x^5]+[x^0]right)(1+x+x^2)(1+x^2+x^4+x^6)tag2\
&=left([x^5]+[x^0]right)(colorblue1+x+x^2)(colorblue1+x^2+x^4+x^6)tag3\
&=1+[x^5](1+colorbluex+x^2)(1+x^2+colorbluex^4+x^6)tag4\
&=1+1tag5\
&,,colorblue=2
endalign*
Comment:
In (1) we multiply out the terms with the highest powers which is convenient as we will see in step (3).
In (2) we use the linearity of the coefficient of operator and apply the rule $[x^p-q]A(x)=[x^p]x^qA(x)$.
In (3) we can skip $[x^15]$ and $[x^10]$ since they do not contribute as the highest power of $x$ is $8$.
In (4) we select the coefficient of $x^0$.
In (5) we select the coefficient of $x^5$.
answered 2 days ago
Markus Scheuer
55.7k450135
This is a supplement to the already given answer showing that calculating the coefficient is not that cumbersome. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial.
We obtain
beginalign*
colorblue[x^15]&colorblue(1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^10)\
&=[x^15](1+x^5+x^10+x^15)(1+x+x^2)(1+x^2+x^4+x^6)tag1\
&=left([x^15]+[x^10]+[x^5]+[x^0]right)(1+x+x^2)(1+x^2+x^4+x^6)tag2\
&=left([x^5]+[x^0]right)(colorblue1+x+x^2)(colorblue1+x^2+x^4+x^6)tag3\
&=1+[x^5](1+colorbluex+x^2)(1+x^2+colorbluex^4+x^6)tag4\
&=1+1tag5\
&,,colorblue=2
endalign*
Comment:
In (1) we multiply out the terms with the highest powers which is convenient as we will see in step (3).
In (2) we use the linearity of the coefficient of operator and apply the rule $[x^p-q]A(x)=[x^p]x^qA(x)$.
In (3) we can skip $[x^15]$ and $[x^10]$ since they do not contribute as the highest power of $x$ is $8$.
In (4) we select the coefficient of $x^0$.
In (5) we select the coefficient of $x^5$.
answered 2 days ago
Markus Scheuer
55.7k450135
edited 2 days ago
answered 2 days ago
Markus Scheuer
55.7k450135
answered 2 days ago
Markus Scheuer
55.7k450135
answered 2 days ago
Markus Scheuer
55.7k450135
55.7k450135
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
1
Good point (+1). Thank you.
– awkward
yesterday
add a comment |Â
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
1
Good point (+1). Thank you.
– awkward
yesterday
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
but last 6 means 1, actually it should result 2
– Debasis Jana
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
@DebasisJana: Ok, I see. From your example I thought you wanted to distinguish them.
– Markus Scheuer
2 days ago
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
But in terms of computation how do I solve it? If I do polynomial multiplication then it will be a brute force approach. What is the efficient algorithm?
– Debasis Jana
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
@DebasisJana: As long as there is a moderate number of terms involved as in this example the brute force approach is presumably the most appropriate. Somewhat more sophisticated techniques could implement a cut off of branches as it done in the calculation from step 2 to step 3.
– Markus Scheuer
yesterday
1
1
Good point (+1). Thank you.
– awkward
yesterday
Good point (+1). Thank you.
– awkward
yesterday
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871795%2fcoin-change-with-fixed-denominations-with-duplicate-values%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
dynamic programming geeksforgeeks.org/dynamic-programming-subset-sum-problem
– Debasis Jana
2 days ago
Your DP answer repeats combinations, suggesting that you are thinking of the coins with the same value as different from each other. The "actual result" suggests they are the same. And you're missing combinations with $(1,1)$ replacing a $(2)$. Please edit the question to clarify. That said, I suspect there is no good algorithm to count what you want.
– Ethan Bolker
2 days ago