3.2 Factor Combinations

e.g. target = 12, return {{2,6}, {3,4}, {2,2,3}} Note: duplicate combination is not allowed.

Input: int target

Output: List<List<Integer>> all possible factor combinations

Corner case: if target <= 1, return first

Solution:

1. Pre-process the target number to get all factors (ask if 1xtarget included)

2. # of factors: m

m levels of the tree, each level consider one factor

states/branches are dynamically changing

TC: n=target m=# of factors O(n^m) worst

SC: O(m)

public List<List<Integer>> combinations(int target) {
  List<List<Integer>> res = new ArrayList<>();
  //corner case
  if (target <= 1) {
    return res;
  }
  List<Integer> cur = new ArrayList<>();	//solution prefix
  List<Integer> factors = getFactors(target); 	//find all factors
  helper(target, factors, 0, cur, res);
  return res;
}

private List<Integer> getFactors(int target) {
  List<Integer> factors = new ArrayList<>();
  //stop checking at half point
  for (int i = target / 2; i > 1; i--) {
    if (target % i == 0) {
      factors.add(i);
    }
  }
  return factors;
}

private void helper(int remain, List<Integer> factors, int index, List<Integer> cur, List<List<Integer>> res) {
  //base case
  if (index == factors.size()) {
    if (remain == 1) {
      res.add(new ArrayList<>(cur));
    }
    return;
  }

  helper(remain, factors, index + 1, cur, res);
  int factor = factors.get(index);
  int size = cur.size(); 			// record size for easy remove later
  while (remain % factor == 0) {
    cur.add(factor);
    helper(remain /= factor, factors, index + 1, cur, res);
  }
   cur.subList(size, cur.size()).clear();   //remove added factor, subList(fromIndex, toIndex).clear()
}