Sunday, October 30, 2016

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.

Backtracking. Note since we only iterate till i * i <= n, we need to add n to the result to get 1 * n = n. Note this operation is used to get the remaining numbers. For example, 2 * 2 * 3 = 12, now n = 3 and i starts with 2, 2 * 2 > 3, so the function will exit the loop. we need to add 3 to the result to get the final one.


public List> getFactors(int n) {
        List> rst = new ArrayList<>();
        if (n < 2) {
            return rst;
        }
        getFactors(rst, n, new ArrayList<>());
        return rst;
    }

    private void getFactors(List> rst, int n, List curr) {
        if (n == 1) {
            if (curr.size() > 1) {
                rst.add(new ArrayList<>(curr));
            }
            return;
        }
        for (int i = 2; i * i <= n; i++) {
            if (!curr.isEmpty() && i < curr.get(curr.size() - 1)) {
                continue;
            }
            if (n % i == 0) {
                curr.add(i);
                getFactors(rst, n / i, curr);
                curr.remove(curr.size() - 1);
            }
        }
        curr.add(n);
        getFactors(rst, 1, curr);
        curr.remove(curr.size() - 1);
    }


No comments:

Post a Comment