@@ -0,0 +1,2283 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Numbers can be regarded as product of its factors. For example,%0A * %3Cp%3E%0A * 8 = 2 x 2 x 2;%0A * = 2 x 4.%0A * Write a function that takes an integer n and return all possible combinations of its factors.%0A * %3Cp%3E%0A * Note:%0A * You may assume that n is always positive.%0A * Factors should be greater than 1 and less than n.%0A * %3Cp%3E%0A * Examples:%0A * input: 1%0A * output:%0A * %5B%5D%0A * input: 37%0A * output:%0A * %5B%5D%0A * input: 12%0A * output:%0A * %7C%5B%0A * %7C  %5B2, 6%5D,%0A * %7C  %5B2, 2, 3%5D,%0A * %7C  %5B3, 4%5D%0A * %7C%5D%0A * input: 32%0A * output:%0A * %7C%5B%0A * %7C  %5B2, 16%5D,%0A * %7C  %5B2, 2, 8%5D,%0A * %7C  %5B2, 2, 2, 4%5D,%0A * %7C  %5B2, 2, 2, 2, 2%5D,%0A * %7C  %5B2, 4, 4%5D,%0A * %7C  %5B4, 8%5D%0A * %7C%5D%0A * %3Cp%3E%0A * Company Tags: LinkedIn, Uber%0A * Tags: Backtracking%0A * Similar Problems: (M) Combination Sum%0A */%0Apublic class FactorCombinations %7B%0A%0A    /**%0A     * Backtracking.%0A     * Factors are from 2 to sqrt(n), inclusive.%0A     */%0A    public List%3CList%3CInteger%3E%3E getFactors(int n) %7B%0A        List%3CList%3CInteger%3E%3E factors = new ArrayList%3C%3E();%0A        backtrack(factors, n, 2, new ArrayList%3C%3E());%0A        return factors;%0A    %7D%0A%0A    /**%0A     * Stop condition:%0A     * n is 1, return. If have at least two factors, dereference and add to result.%0A     * Visit:%0A     * For each i from start to sqrt(n):%0A     * %7C If n is divisible by i:%0A     * %7C   Add i to factors.%0A     * %7C   backtrack on n / i, starting from i. (12 -%3E 2, 2, 3)%0A     * %7C   Reset.%0A     * %7C If n is not divisible by i, skip.%0A     * Special case:%0A     * Besides %5Bstart, sqrt(n)%5D, n itself can also be a factor.%0A     */%0A    private void backtrack(List%3CList%3CInteger%3E%3E res, int n, int start, List%3CInteger%3E factors) %7B%0A        if (n == 1) %7B%0A            if (factors.size() %3E 1) %7B // If n=1, return empty list.%0A                res.add(new ArrayList%3C%3E(factors));%0A            %7D%0A            return;%0A        %7D%0A%0A        for (int i = start; i %3C= (int) Math.sqrt(n); i++) %7B%0A            if (n %25 i == 0) %7B%0A                factors.add(i);%0A                backtrack(res, n / i, i, factors);%0A                factors.remove(factors.size() - 1);%0A            %7D%0A        %7D%0A        int i = n; // ===%3E here, change 2%0A        factors.add(i);%0A        backtrack(res, n / i, i, factors);%0A        factors.remove(factors.size() - 1);%0A    %7D%0A%7D%0A

add factor combinations