# Factor Combinations

Leave a commentFebruary 20, 2017 by oneOokay

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*.

**Examples: **

input: `1`

output:

[]

input: `37`

output:

[]

input: `12`

output:

[ [2, 6], [2, 2, 3], [3, 4] ]

input: `32`

output:

[ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]

挺容易想到用backtracking,但是有这个两个问题:

- 怎么处理质数
- backtracking如何确保结果不重复:
- 要把factor也包含在helper method里面.
- for-loop的时候i从factor开始
- i的上限为(int)Math.sqrt(number)

- 什么时候加入把list加入到结果中

public List<List> getFactors(int n) { List<List> ans = new ArrayList<>(); helper(n, 2, new ArrayList(), ans); return ans; } public void helper(int number, int factor, List list, List<List> ans){ //传入factor && i从factor开始 && i<=(int)Math.sqrt(number) //保证了结果不重复:结果都是递增的也保证了质数不会被加到结果中 for (int i = factor; i <= (int)Math.sqrt(number); i ++){ if (number % i == 0){ list.add(i); list.add(number / i); ans.add(new ArrayList(list));//把list加入到ans的时机 list.remove(list.size() - 1); //移除一个factor helper(number / i, i, list, ans);//继续dfs list.remove(list.size() - 1);//移除另外一个 } } }

Advertisements