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

// O(n*value) -> Space solution
public class Solution {
    long mod = 1000007;

    public int coinchange2(int[] coins, int sum) {
        long dp[][] = new long[coins.length + 1][sum + 1];
        // Base case -> If value=0 then only 1 way is possible
        // 2nd base case if number of coins=0 then ways=0
        for (int i = 0; i <= coins.length; i++)
            dp[i][0] = 1;
        for (int i = 0; i <= coins.length; i++) {
            for (int j = 1; j <= sum; j++) {
                // option 1 -> dont inculde the current coin
                dp[i][j] = (dp[i - 1][j]) % mod;
                // option 2 -> include the current coin (if you can)
                if (j - coins[i] >= 0)
                    dp[i][j] = (dp[i][j] + dp[i][j - coins[i]]) % mod;
            }
        }
        return (int) ((dp[coins.length][sum]) % mod);
    }
}

// O(n) -> Space solution
public class Solution {
    long mod = 1000007;

    public int coinchange2(int[] coins, int sum) {
        long dp[] = new long[sum + 1];
        // Base case -> If value=0 then only 1 way is possible
        dp[0] = 1;
        for (int x : coins) {
            for (int s = 1; s <= sum; s++) {
                if (s - x >= 0)
                    dp[s] = (dp[s] + dp[s - x]) % mod;
            }
        }
        return (int) ((dp[sum]) % mod);
    }
}