My code:
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (n <= 1) {
return ret;
}
helper(2, n, new ArrayList<Integer>(), ret);
return ret;
}
private void helper(int begin, int n, List<Integer> group, List<List<Integer>> ret) {
if (n == 1) {
if (group.size() > 1) {
ret.add(new ArrayList<Integer>(group));
}
return;
}
for (int i = begin; i <= n; i++) {
if (n % i == 0) {
group.add(i);
helper(i, n / i, group, ret);
group.remove(group.size() - 1);
}
}
}
}
reference:
https://discuss.leetcode.com/topic/21082/my-recursive-dfs-java-solution
这道题目一开始我的做法是，从底向上， backtracking,肯定是可以做出来的。但是，因为无法判断每个branch的最终结果，我都需要尝试，复杂度太大，导致栈溢出。
而答案中给的解法，很聪明，从顶向下，如果不能整除，直接就忽略了，而不需要给他分配额外的栈做recursive call
而且随着recursive depth越来越深，遍历的范围也会越来越小。
这么做，recursive call 次数肯定要少很多很多。
因为，他尽最大努力，往着正确方向走。
Anyway, Good luck, Richardo! -- 09/19/2016
