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).

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

Solution:

public class Solution {
    public int coinchange2(int[] A, int B) {
        // dp[i][B] = number of ways using 0 - ith coin for form B
        // dp[i][B] = (A[i] == B ? 1 : 0) + dp[i - 1][B] + dp[i][B - A[i]]
        // dp[0][0] = 1, dp[i][0] = 0, dp[0][j] = 0
        // dp[n][B]
        int MOD = 1000007;
        int n = A.length;
        int[][] dp = new int[n + 1][B + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= B; j ++) {
                if (A[i - 1] == j) {
                    dp[i][j] = 1;
                }
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                if (j - A[i - 1] >= 0) {
                    dp[i][j] = (dp[i][j] + dp[i][j - A[i - 1]]) % MOD;
                }
            }
        }
        // for (int[] arr: dp) {
        //     System.out.println(Arrays.toString(arr));
        // }
        return dp[n][B];
    }
}