[LeetCode] 254. 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:

1. You may assume that n is always positive.
2. Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

因子的组合。题意是给一个整数N，请你返回他所有的因子组合。

思路是回溯。我这里首先提供一个未剪枝的做法。代码还是用到大部分回溯类的题都需要用的模板，需要用到一个helper函数。函数中的N的含义是试图被整除的数字。

时间O(n!)

空间O(n)

Java实现

注意17行为什么i <= n而不是i < n，可以这样想，如果N是2的话，i又是从2开始，如果没有等号的话，这个for loop都进不去，所以需要有等号。

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

    // n - the number we are trying to divide
    // start = the first dividor we try
    private void helper(List<List<Integer>> res, List<Integer> list, int n, int start) {
        if (n == 1) {
            if (list.size() > 1) {
                res.add(new ArrayList<>(list));
                return;
            }
        }
        for (int i = start; i <= n; i++) {
            if (n % i == 0) {
                list.add(i);
                helper(res, list, n / i, i);
                list.remove(list.size() - 1);
            }
        }
    }
}

其次是一个剪枝了的做法，速度提高不少。注意16行，在遍历一个数字的因数的时候，其实当你找到第一个大于1的因数i的时候，最大的因数就是这个数字除以i。举个例子，比如你找到了8的最小因数2，8的最大因数会是8 / 2 = 4。但是为什么这个剪枝了的做法的base case会跟前一种做法不一样呢？还是拿8举例子，i在递归函数里会是这样变化的

第一轮一开始16行i = 2, i <= 16 / 2 = 8，进入19行的时候，n / i = 8 / 2 = 4

第二轮递归的时候，i = 2，i <= n / i = 4 / 2 = 2

这样会导致再下一轮递归的时候，如果i继续等于2的话，n / i = 2 / 2 = 1，会导致16行的for loop根本跑不起来。此时list里面只有两个2，但是为了得到8，其实你需要3个2。

Java实现

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

    // n - the number we are trying to divide
    // start = the first dividor we try
    private void helper(List<List<Integer>> res, List<Integer> list, int n, int start) {
        if (!list.isEmpty()) {
            list.add(n);
            res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
        }
        for (int i = start; i <= n / i; i++) {
            if (n % i == 0) {
                list.add(i);
                helper(res, list, n / i, i);
                list.remove(list.size() - 1);
            }
        }
    }
}

LeetCode 题目总结