今天和大家聊的问题叫做 因子的组合，我们先来看题面：https://leetcode-cn.com/problems/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.
请实现一个函数，该函数接收一个整数 n 并返回该整数所有的因子组合。
示例
你可以假定 n 为永远为正数。 因子必须大于 1 并且小于 n。 示例 1： 输入: 1 输出: [] 示例 2： 输入: 37 输出: [] 示例 3： 输入: 12 输出: [ [2, 6], [2, 2, 3], [3, 4] ] 示例 4: 输入: 32 输出: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]
解题
可以采用递归。从2开始遍历到sqrt(n)，能被n整除就进下一个递归，当start超过sqrt(n)时，start变成n，进下一个递归。
public class Solution { public List<List<Integer>> getFactors(int n) { List<List<Integer>> result = new ArrayList<List<Integer>>(); helper(result, new ArrayList<Integer>(), n, 2); return result; } public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){ if (n <= 1) { if (item.size() > 1) { result.add(new ArrayList<Integer>(item)); } return; } for (int i = start; i * i <= n; ++i) { if (n % i == 0) { item.add(i); helper(result, item, n/i, i); item.remove(item.size()-1); } } int i = n; item.add(i); helper(result, item, 1, i); item.remove(item.size()-1); } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
