0

There is one important point - We can pick any element any number of times but the total picked element should be equal to K.

For example - If set of elements is 1 2 3 5 and K = 3 and X = 4.

Then answer is 1 because there is only one way to pick 3 elements which adds upto 4 and those 3 elements are two 1's and one 2. (1+1+2 = 4)

An algorithm can greatly help. :)

Godfather
  • 5,711
  • 5
  • 21
  • 27
  • This paper may give some direction. http://www.iaeng.org/IJAM/issues_v40/issue_1/IJAM_40_1_01.pdf – Abhishek Bansal May 12 '16 at 17:41
  • Just modify `coin change problem` solution, taking coin number limit into account. – MBo May 12 '16 at 18:05
  • I know the coin change problem (using dp) but how can i modify that to solve the above problem. – Godfather May 12 '16 at 18:10
  • Since you want the number of possible solutions, rather than a solution, you'll have to try every possible (valid) combination and count the number of solutions. You can prune it down based on the criteria, since you know exactly how many elements to choose for each combination, and since you can eliminate impossible values from the set of elements. Dynamic programming isn't likely to help, because your restrictions are opposite of the coin change problem (coin change has set of non-repeatable elements, with any number summing to X; yours has repeatable elements with fixed number summing). – Matt Jordan May 12 '16 at 18:34
  • http://stackoverflow.com/questions/4243831/how-to-count-possible-combination-for-coin-problem/ – גלעד ברקן May 31 '16 at 23:28

1 Answers1

0

Let's consider DP solution for coin change problem. Usually entries of array A with length (Sum+1) contain integers - number of ways to make the value of every cell.

Simple modification - make 2D array A[Sum+1][K], so A[M][P] will contain number of ways to make value M using P coins.

MBo
  • 77,366
  • 5
  • 53
  • 86