CoinChangePattern.java

/*
    Problem: Given denominators (coins) and an amount,
    find how many patterns are there.

    Optimal Substructure
        1) Solutions that contain i-th coin
        2) Solutions that do not contain i-th coin
 */
public class CoinChangePattern {
    // complexity: time O(2^n), space: O(n)
    static int findPatternsRecur(int[] coins, int n, int S) {
        // base case, amount = 0
        if (S == 0) {
            return 1;
        }
        if (S < 0) {
            return 0;
        }
        if (n <= 0 && S >= 1) {
            return 0;
        }
        return findPatternsRecur(coins, n, S-coins[n-1]) +
                findPatternsRecur(coins, n-1, S);
    }
    
    // complexity: time O(n*m), space O(n*m), n: number of coins, m: sum
    static int findPatterns(int[] coins, int S) {
        int[][] memo = new int[coins.length+1][S +  1];
        // base case S = 0
        for (int i=0; i<=coins.length; i++) { memo[i][0] = 1; }
        // base case coins are empty
        for (int i=1; i<=S; i++) { memo[0][i] = 0; }
        int x, y;
        for (int s = 1; s <= S; s++) {
            for (int i=1; i<=coins.length; i++) {
                // count of solutions including coins[i]
                x = (coins[i-1] <= s) ? memo[i][s - coins[i-1]] : 0;
                // count of solutions excluding coins[i]
                y = memo[i - 1][s];
                memo[i][s] = x + y;
            }
        }
        return memo[coins.length][S];
    }
  
    public static void main(String[] args) {
        int S = 5;
        int[] coins = {1, 2, 3};
        System.out.println(findPatternsRecur(coins, coins.length, S));
        System.out.println(findPatterns(coins, S));
        S = 4;
        System.out.println(findPatternsRecur(coins, coins.length, S));
        System.out.println(findPatterns(coins, S));
    }
}