0254. Factor Combinations

https://leetcode.com/problems/factor-combinations

Description

Numbers can be regarded as the product of their factors.

• For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Example 1:

**Input:** n = 1
**Output:** []

Example 2:

**Input:** n = 12
**Output:** [[2,6],[3,4],[2,2,3]]

Example 3:

**Input:** n = 37
**Output:** []

Example 4:

**Input:** n = 32
**Output:** [[2,16],[4,8],[2,2,8],[2,4,4],[2,2,2,4],[2,2,2,2,2]]

Constraints:

• 1 <= n <= 107

ac

// KEY: circumvent repeat, number always <= next one
class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> note = new ArrayList<Integer>();

        backtrack(res, note, n, 2);

        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> note, int n, int s) {
        // exit
        if (n <= 1) {
            if (note.size() > 1) {
                res.add(new ArrayList<Integer>(note));
            }
            return;
        }

        //  handle
        for (int i = s; i <= n; i++) {
            if (n % i == 0) {
                note.add(i);
                backtrack(res, note, n / i, i);
                note.remove(note.size()-1);
            }
        }
    }
}

ac2:

key: i = start; i <= n/i ensure acending list

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

    private void helper(int n, int start, List<Integer> note, List<List<Integer>> res) {
        // exit
        if (note.size() > 0) {
            List<Integer> tmp = new ArrayList<Integer>(note);
            tmp.add(n);
            res.add(tmp);
        }

        for (int i = start; i <= n/i; i++) { // i <= n/i, list should be ascending
            if (n % i != 0) continue;
            note.add(i);
            helper(n / i, i, note, res);
            note.remove(note.size()-1);
        }
    }
}