254. Factor Combinations

 一刷 07/2022

Version #1 Backtracking

自己想的时候先计算了一下小于等于sqrt(n)的所有factor

然后每次取一些factor和它们的remainder组成一组答案，要求remaider必须大于等于factor来保证没有重复答案

看了其他人的做法不需要提前算出factor，只要在i和n之间iterate找到能整除的数 感觉这个做法比较慢

Time O(logN^logN) given that we have logN number of factors and we called the recursive function time complexity of a recursive function = number of choices ^ number of steps

Space O(logN)

Runtime: 5 ms, faster than 90.58% of Java online submissions for Factor Combinations.

Memory Usage: 54.2 MB, less than 22.28% of Java online submissions for Factor Combinations.

class Solution {

    public List<List<Integer>> getFactors(int n) {

        List<Integer> factors = new ArrayList<>();

        for (int i = 2; i <= Math.sqrt(n); i++) {

            if (n % i == 0) {

                factors.add(i);

            }

        }

        List<List<Integer>> result = new ArrayList<>();

        select(factors, 0, new ArrayList<>(), n, result);

        return result;

    }

    

    private void select(List<Integer> factors, int index, List<Integer> path, int target, List<List<Integer>> result) {

        if (path.size() > 0) {

            path.add(target);

            result.add(new ArrayList<>(path));

            path.remove(path.size() - 1);

        }

        for (int i = index; i < factors.size(); i++) {

            int f = factors.get(i);

            if (target % f != 0) {

                continue;

            }

            if (target / f < f) {

                break;

            }

            path.add(f);

            select(factors, i, path, target / f, result);

            path.remove(path.size() - 1);

        }

    }

}