Factor Combinations

Leave a comment

February 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:

  1. You may assume that n is always positive.
  2. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: