Coin change

Submit solution
Points: 15
Time limit: 1.0s
Memory limit: 256M
Author:
moncef
Problem type

You have a sum of money \(S\) and an infinite supply of coins with denominations \(a[i]\), in how many ways you can make the sum \(S\) using the given denominations.

Two ways are considered different if the number of coins with a given denomination used in one way is different than the other way.

Imagine having \(S = 4\) and we have coins with denominations \(a = \{1, 2, 3\}\), there are 4 ways to make the sum using the given denominations:

  • \([1,1,1,1]\)
  • \([1,1,2]\)
  • \([2,2]\)
  • \([1,3]\)

Note that \([1,3]\) and \([3,1]\) are equivalent and considered as the sam way, order does not matter.

Input Specification

First line contains integer \(1 \leq S \leq 1000\) and \(1 \leq K \leq 100\) the sum of money you have and the number of coin denominations. The second line contains \(K\) distinct integers representing the coin denominations \(1 \leq a[i] \leq S\)

Output Specification

Print one integer representing the number of ways to make change for \(S\).

Since this number can too big, print it modulo \(10^{9} + 7\)

Sample Input

4 3
1 2 3

Sample Output

4

Sample Input

2 1
1

Sample Output

1

Sample Input

6 4
1 3 4 2

Sample Output

9

Comments


  • 0
    DrAymeinstein  commented on Nov. 19, 2023, 6:05 p.m.

    Can someone help? I get "[RTE] Segmentation Error" Dans case 4. Can someone see what is wrong with my code? https://ideone.com/g14chK Thank you very much.


    • 1
      AkramElOmrani  commented on Nov. 20, 2023, 11:06 a.m.

      Just change your dp array size dp[1001][101]


      • 0
        DrAymeinstein  commented on Nov. 20, 2023, 6:36 p.m.

        Thank you a lot :) It worked