/**
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()));
}
}
}
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