原题链接
题目原文:
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:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Example 1: Input:1Output:[]
Example 2: Input:37Output:[]
Example 3: Input:12Output:[ [2, 6], [2, 2, 3], [3, 4]]
Example 4: Input:32Output:[ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8]]
中文翻译:
数字可以被看作是它的约数的乘积。举个例子:
8 = 2 x 2 x 2;
= 2 x 4.
写一个函数,带一个整形参数n, 返回所有可能的约数组合。
注意:
你可以假设n总是正的。约数应该大于1并且小于n。
例子自己看上面的吧,以后这部分没有必要的话,尽量就不翻译了。
其实从Test case里,我们已经能看出一些解答的端倪,
首先,每个解答里面的约数都介于2~n - 1, 并且是按顺序从左到右递增。
那么思路就是对于数字n, 并且把当前解答里最后一个元素的值设为bound, n则需要找到 bound ~ sqrt (n)范围内的约数。这里sqrt(n)则是n的开根号,因为数字是递增的,所以不能够允许剩余的数字小于bound