Factor Combinations

一道陈年老题了，这道题在LeetCode上的数据规模是不需要做任何额外检查就能过的，不过必须用Java，另外每次除法之后的上限要随之缩小，这样可以节省非常多的不必要循环，lintcode的数据规模太大，下面的代码没法通过

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        ArrayList<Integer> tmp = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(2, n, tmp, result);
        return result;
    }

    void helper(int start, int end, List<Integer> tmp, List<List<Integer>> result) {
        if (end == 1 && tmp.size() > 1) {
            ArrayList<Integer> ref = new ArrayList<Integer>(tmp);
            result.add(ref);
            return;
        }

        for (int i = start; i <= end; ++i) {
            if (end % i != 0) {
                continue;
            }

            tmp.add(i);
            helper(i, end / i, tmp, result);
            tmp.remove(tmp.size() - 1);
        }
    }
}

此题在回溯里面属于最麻烦的一道题了，因为小细节的改进有很多方法，比如关于end这个for循环的上界其实是有很多冗余的，我们可以把循环的范围缩小到end / i（Python不能用这样的语法），能这么写的原因暂时还不太清楚，下面是优化了很多之后的代码，可以通过lintcode的大数据检测

public class Solution {
    /**
     * @param n an integer
     * @return a list of combination
     */
    public List<List<Integer>> getFactors(int n) {
        // write your code here
        ArrayList<Integer> tmp = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        helper(2, n, tmp, result);
        return result;
    }

    void helper(int start, int end, List<Integer> tmp, List<List<Integer>> result) {
        if (!tmp.isEmpty()) {
            tmp.add(end);
            result.add(new ArrayList<>(tmp));
            tmp.remove(tmp.size() - 1);
        }

        for (int i = start; i <= end / i; ++i) {
            if (end % i == 0) {
                tmp.add(i);
                helper(i, end / i, tmp, result);
                tmp.remove(tmp.size() - 1);
            } 
        }
    }
}

这里用了一种类似subset的做法，即只要tmp不是空的，立即把结果输出，这种逻辑在回溯里面用的比较少，而且这里利用了Java for循环的特性动态缩减了循环的上界，这一点在Python里面的for循环是做不到的