trcfx9's blog

Coin Combinations II
By trcfx9, history, 3 years ago, In English

How to solve it recursively, is it possilbe or not? I tried a long time but dint came up a solution.

Problem Link: https://cses.fi/problemset/task/1636

And what does it mean my this line "the number of distinct ordered ways". It means increaing order or decreasing order?

THanks in Advance

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Number of distinct ordered ways means order does not matter. For example if sum = 4 then 1 2 1 and 1 1 2 and 2 1 1 is considered same and counted one time. Read this tutorial https://codeforces.com/blog/entry/70018

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me the recursive solution of the problem?

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

To anyone else, having confusion with "the number of distinct ordered ways", it means the ordered ways to use the available coins. For example, given coins = [2,3,5] Coin 2 must be used before 3, 3 before 5 and so on. So: 2 + 3 + 5 and 2 + 2 + 3 is acceptable, But 2 + 3 +2 is Not. and you have to find distinct ways order ways to find answer this way. Hope this helps.

→ Reply