How are the coin change change problem and Ways to sum to N using array elements with repetition allowed giving different answers based on ordering of elements in the subset.
Both of the questions are one and the same except for a slightly different way of framing the problem. Which test case ended up giving different answers?
2 Likes
in the coin change order of coins does not matter while in summation problem order does matter.
eg for arr={1,2,3} and k=3
coin change output = 3
summation output = 4
Don’t you have your answer right there? If the order doesn’t matter {1, 1, 2} and {1, 2, 1} and {2, 1, 1} are counted as 1. If the order matters there are counted as 3. What is your doubt?
1 Like
I am confused how is interchanging the loops giving results based on order.