/ Math

Generate all Factor Combinations

Problem Statement

Given a number 'n', generate all factor combinations.
For example, when n=24, the result would be [[2, 3, 3], [2, 9], [3, 6]]


Solution Explanation

As we know, every integer can be formed by product or multiplication of some numbers. These are considered to be factors of that number.

And every number can multiple combinations of factors. For example, n=18 can be formed by,

    18 = 3 * 6 or 2*3*3 or 2*9

Finding one combination is straightforward, all you would do is, in a loop, check if modulo of 'n' to each number is zero, if it is, then you have a combination.

Our approach to solving the problem involves little extension using recursion where everytime we find a 'j' where n/j=0, we pass the n/j as 'n' to the method. We recurse until n<=1.

Below is the full java implementation of generating factors,

public class FactorCombinations {

	public static void main(String[] args) {
		System.out.println(new FactorCombinations().getFactors(18));

	}

	public List<List<Integer>> getFactors(int n) {
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> temp = new ArrayList<>();
		helper(result, temp, n, 2);
		return result;
	}

	public void helper(List<List<Integer>> result, List<Integer> temp, int n, int start) {
		//When n<=1, we reach the end of one recursion, so we add temp to main result.
		if (n <= 1) {
			if (temp.size() > 1) {
				result.add(new ArrayList<Integer>(temp));
			}
		}

		for (int i = start; i <= n; i++) {
			//When n%i is 0, pass n/i as 'n'
			if (n % i == 0) {
				temp.add(i);
				helper(result, temp, n / i, i);
				//This step is important to remove the older entry and generate a new combination of factors.
				temp.remove(temp.size() - 1);
			}
		}
	}

}
Output

The output for the above code is

[[2, 3, 3], [2, 9], [3, 6]]

Time Complexity

The time complexity is O(n).