Share my concise JAVA backtracking solution with commens


  • 0
    G

    public class FactorCombinations {

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(n, ans, new ArrayList<>());
        return ans;
    }
    
    public void backtrack(int n, List<List<Integer>> ans, List<Integer> branch) {
    
        // A little bit different from traditional backtracking, as long as branch is not empty, we accept the combination.
        if (branch.size() > 0) {
            branch.add(n);
            ans.add(new ArrayList<>(branch));
            branch.remove(branch.size() - 1);
            // We want to continue to break down n, so we can not return here.
        }
        // Start from 2, till the square root of N, skip other bigger numbers to avoid duplication.
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // We want to skip smaller factors to avoid duplication.
            // Eg. if n = 32, [4, 8] is valid, but we want to skip [4, 2, 4] and [4, 2, 2]
            if (n % i == 0 && (branch.isEmpty() || branch.get(branch.size() - 1) <= i)) {
                branch.add(i);
                backtrack(n / i, ans, branch);
                branch.remove(branch.size() - 1); // Backtrack the last factor
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.