3.1 Coins combination

e.g. target = 99 [25, 10, 5, 1]

one possible way 25x3 10x2 5x0 1x4

Assumption:

1. no duplicate in coin values, array in descending order, not null, not empty, all positive

2. target >= 0

Input: int[] coin values, int target value

Output: List<List<Integer>> possible combination of coins, the index indicate corresponding coin value in the array

Solution:

1. # of denomination of levels in the tree, each level consider how many possible cases for that one denomination that's chosen

2. branches dynamically changing, at most n branches

3. If there's duplication in denomination, sort the array and add a condition check to skip.

TC: target = n, # of coin denomination = m O(n^m) worst

SC: m on stack, m on heap(cur) O(m)

public List<List<Integer>> combinations(int target, int[] coins) {
  List<List<Integer>> res = new ArrayList<>();
  List<Integer> cur = new ArrayList<>();	//prefix solution
  helper(target, coins, 0, cur, res);
  return res;
}

private void helper(int remain, int[] coins, int index, List<Integer> cur, List<List<Integer>> res) {
  //base case: terminate when considering the last denomination
  if (index == coins.length - 1) {
    if (remain % coins[coins.length - 1] == 0) {
      cur.add(remain / coins[coins.length - 1]);
      res.add(new ArrayList<Integer>(cur));		// deep copy
      cur.remove(cur.size() - 1);
    }
    return;
  }

   //for denomination 'coins[index]', pick 0 ~ (remain / coins[index]) amount
   // i: amount picked
   for (int i = 0; i <= remain / coins[index]; i++) {
     cur.add(i)
     helper(remain - i * coins[index], coins, index + 1, cur, res);
     cur.remove(cur.size() - 1)
   }
}