Coin Sum Infinite

You are given a set of coins S. In how many ways can you make sum N assuming you have infinite amount of each coin in the set.

Note : Coins in set S will be unique. Expected space complexity of this problem is O(N).

Example :

Input : 
	S = [1, 2, 3] 
	N = 4

Return : 4

Explanation : The 4 possible ways are
{1, 1, 1, 1}
{1, 1, 2}
{2, 2}
{1, 3}	

Note that the answer can overflow. So, give us the answer % 1000007

Interview Code Editor
Hints
  • Hint 1
  • Solution Approach
  • Complete Solution
2864 successful submissions.
Asked In:
  • Microsoft
Click here to jump start your coding interview preparation