LeetCode 254 Factor Combinations (LintCode 652 Factorization)

思路

枚举类dfs+剪枝。dfs部分思路很简单，从小到大枚举即可保证题目中的非降序的要求。但是要注意每次dfs要对target进行重新计算，除以添加到path的数。
剪枝：提前判断i和target/i的关系（即下一层dfs的后两个变量的大小关系），因为在进入for循环之后就可以立即计算出来这两个参数，在这里剪枝之后可以避免path的add和remove操作，还是有一定作用的。但是这样会误伤dfs(i, 1)的情况，所以需要在for之后进行修补（具体见代码）。eg：dfs(2,8)->dfs(2,4)->dfs(2,2)->dfs(2,1)->…，在这个序列中，走到dfs(2,2)就会break，在修补部分直接拿target作为i，因为一定是首先经过target==i的时候break，下一步如果不break的就是dfs(i, 1)了，所以可以直接拿target，还是可以参考上面的例子。

代码

LintCode 652 代码

public class Solution {
    /*** @param n: An integer* @return: a list of combination*/public void dfs(List<List<Integer>> res, List<Integer> path, int base, int target) {
    if(target == 1) {
    if(path.size() > 1) {
    // avoid the case: input = 8, output = [8].res.add(new ArrayList<>(path));}return;}for(int i = base; i <= target; i++) {
    // 剪枝操作// 下一层dfs的后两个参数可以在这里就计算出来：i和target / i// 基于for中是递增循环的，所以下一层dfs的后两个参数一旦base > target// 那么就说明不符合要求，就不需要add和remove操作了// 但是会误伤target / i == 1的情况，导致不能进入dfs的递归出口// 不能在下面的if中直接写target / i == 1的情况，因为==1的情况是在其他// 满足break的情况之后才出现(最后出现), 所以有可能没有机会执行到这个条件if(i > target / i) break;if(target % i == 0) {
    path.add(i);dfs(res, path, i, target / i);path.remove(path.size() - 1);}}// 修补上面剪枝操作的误伤path.add(target);dfs(res, path, target, 1);path.remove(path.size() - 1);}public List<List<Integer>> getFactors(int n) {
    // write your code hereList<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(res, path, 2, n);return res;}
}

复杂度

时间复杂度O(NlogN): T(N) = T(N/2) + T(N/3) + … + T(N/N)
空间复杂度O(logN)

复杂度分析，参考链接：
https://stackoverflow.com/questions/45662736/how-to-find-the-time-complexity-of-dfsbacktracking-algorithms

https://www.jiuzhang.com/qa/5224/