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:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Backtracking. Note since we only iterate till i * i <= n, we need to add n to the result to get 1 * n = n. Note this operation is used to get the remaining numbers. For example, 2 * 2 * 3 = 12, now n = 3 and i starts with 2, 2 * 2 > 3, so the function will exit the loop. we need to add 3 to the result to get the final one.
public List> getFactors(int n) { List
> rst = new ArrayList<>(); if (n < 2) { return rst; } getFactors(rst, n, new ArrayList<>()); return rst; } private void getFactors(List
> rst, int n, List
curr) { if (n == 1) { if (curr.size() > 1) { rst.add(new ArrayList<>(curr)); } return; } for (int i = 2; i * i <= n; i++) { if (!curr.isEmpty() && i < curr.get(curr.size() - 1)) { continue; } if (n % i == 0) { curr.add(i); getFactors(rst, n / i, curr); curr.remove(curr.size() - 1); } } curr.add(n); getFactors(rst, 1, curr); curr.remove(curr.size() - 1); }
No comments:
Post a Comment