254. Factor Combinations

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> results = new ArrayList<>();
        if (n <= 3) {
            return results;
        }

        getFactors(n, 2, new ArrayList<Integer>(), results);
        return results;
    }

    private void getFactors(int n, int start, List<Integer> current, List<List<Integer>> results) {
        if (n == 1) {
            // Factor should be in range of [2, n] therefore if there is only one facotr in
            // the current list, we shouldn't consider this case
            if (current.size() > 1) {
                results.add(new ArrayList<Integer>(current));
            }
            return;
        }

        for (int i = start; i <= (int) Math.sqrt(n); i++) { // ==> here, change 1
            if (n % i != 0) {
                continue;
            }
            current.add(i);
            getFactors(n / i, i, current, results);
            current.remove(current.size() - 1);
        }

        int i = n; // ===> here, change 2
        current.add(i);
        getFactors(n / i, i, current, results);
        current.remove(current.size() - 1);
    }
}

这个的思路是这样的. 对于n, 它可能有的factor假设为a, b, c… 于是combination可以是我们先选a, 这样问题简化为了n / a的factor的combination有哪些. 我们在这些combination之前加上2即可. 当然我们也可以选b, c作为开头. 那问题是如何找到这些factor呢? 一开始我们从2遍历. 找到factor后, 我们需要找n / factor的所有combinaiton. 等到返回回来时我们继续找下一个. 需要注意的是n / factor找它的factor的时候就需要从该factor起去找而不能从2开始, 因为这样会造成重复.

因此我们的原则就是如果某个factor找到, 那么我们可以选它, 它作为开头的所有情况走完后, 我们找下一个factor, 然后让它作为开头继续找. 此时之前出现的factor不能在寻找的范围内了, 因为这样会重复.