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:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
*/
import java.util.*;

public class FactorCombinations{

public static List<List<Integer>> getFactors(int n){
List<List<Integer>> res = new ArrayList<>();
int start = 2;
int prod = 1;
helper(res, new ArrayList<Integer>(), start, prod, n);
return res;
}

public static void helper(List<List<Integer>> res, List<Integer> cur, int start, int prod, int n){
if(start>n || prod>n){
return;
}
if(prod==n){
List<Integer> temp = new ArrayList<Integer>(cur);
res.add(temp);
return;
}
for(int i=start; i<n; i++){
if(i*prod>n){
break;
}
if(n%i==0){
cur.add(i);
helper(res, cur, i, prod*i, n);
cur.remove(cur.size()-1);
}

}

}

public static void main(String args[]){
int n = 8;
List<List<Integer>> factors = getFactors(n);
for(List<Integer> l:factors){
System.out.println(Arrays.toString(l.toArray()));
}

}
}

No comments:

Post a Comment