Very easy to understand 2ms java backtracking solution


  • 8
    S

    The upper bound for the factors of n is (int)sqrt(n), and when you find one factor of n, then put the factor and its corresponding factor to a temp list, and add the temp list to the result list. Then we remove the larger factor from the temp list, and recursively do the larger factor from the smaller factor to upper bound for the same procedure.

    For example, n = 16. Let the variable i be from 2 to 4, when i = 2, then i is one factor of 16, and its corresponding factor is 8, so we add 2 and 8 to a temp list, then add the temp list to the result list. And remove 8 from the temp list, and recursively do 8 from 2 to 2 for the same procedure.

    The result should be:
    [2, 8]
    [2, 2, 4]
    [2, 2, 2, 2]
    [4, 4]

    public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        backTrack(res, new ArrayList<Integer>(), 2, n);
        return res;
    }
    
    public void backTrack(List<List<Integer>> res, List<Integer> cur, int start, int n) {
        int upper = (int)Math.sqrt(n);
        for(int i = start; i <= upper; i++) {
            int factor = -1;
            if(n % i == 0) {
                factor = n/i;
            }
            if(factor != -1 && factor >= i) {
                cur.add(i);
                cur.add(factor);
                res.add(new ArrayList<Integer>(cur));
                cur.remove(cur.size()-1);
                backTrack(res, cur, i, factor);
                cur.remove(cur.size()-1);
            }
        }
    }
    

    }


  • 0
    T

    I like your solution a lot but in the backTrack, "factor >= i" is not really necessary because you have already set an upper bound of i as square root of n.


  • 0
    S

    Yes, you are correct.


Log in to reply
 

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