254. Factor Combinations

 Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

1. You may assume that n is always positive.
2. Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

My answer: didn't figure out solution, only think of sqrt() to restrict choices. Please take a look at the key point below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public List<List<Integer>> getFactors(int n) { List<List<Integer>> result = new ArrayList<List<Integer>>(); helper(2, n , new ArrayList<Integer>(), result); return result; } private void helper(int start, int n, List<Integer> singleResult, List<List<Integer>> result) { // we use i * i < n to make sure the 1st factor of n is in ascending order // and it can avoid duplicate factor // because the larger factor corresponding the smaller factor won't be picked for (int i = start; i * i <= n; i ++) { if (n % i == 0) {// find i as valid factor singleResult.add(i); singleResult.add(n/i); result.add(new ArrayList<Integer>(singleResult)); // backtrack singleResult as we are using i as starting factor singleResult.remove(singleResult.size() - 1); // continue to get factors for n/i // KEY POINT: new start is i // because factor smaller than i must have already shown up in // previous recursion, no need to go over again helper(i, n/i, singleResult, result); // backtrack singleResult as we keep using i as starting factor singleResult.remove(singleResult.size() - 1); } } } }