LC254. 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:
- You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Naive solution：
所有的因子打印出来，那么我的想法就是recursive然后每次将因子作为输入就可以了…
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
helper(res, new ArrayList<Integer>(), n, 2);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> cur, int left, int start){
if(left <= 1){
if(cur.size() > 1)
res.add(new ArrayList<Integer>(cur));
return;
}
for(int i = start; i <= left; i++){
if(left % i == 0){
cur.add(i);
helper(res, cur, left/i, i);
cur.remove(cur.size() - 1);
}
}
return;
}
}
204ms.
Improve:
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> ans = new ArrayList();
if (n < 4){
return ans;
}
DFS(n, ans, 2, new ArrayList<Integer>());
return ans;
}
private void DFS(int n, List<List<Integer>> ans, int factor, List<Integer> entry){
int limit = (int)Math.sqrt(n);
for(int x = factor; x<=limit; x++){
if(n%x == 0){
entry.add(x);
DFS(n/x, ans, x, entry);
entry.add(n/x);
ans.add(new ArrayList(entry));
entry.remove(entry.size()-1);
entry.remove(entry.size()-1);
}
}
}
}
2ms. 利用sqrt函数，每次将一对因子加入结果中～快了好多_(:з」∠)_
DP VS. Backtracking
看了看歪果仁的blog，感觉和逛某乎差不多(笑)
诶呀，有理解错误的地方欢迎捉虫🍪
简而言之，DP是通过将一个问题分解为不重合子问题来解决的方式，通常用于解决具有最优子结构性质的问题。
回溯则搜索了一个问题的所有答案，期间也可以剪枝。