Leetcode - 254. 因子的组合

class Solution {

    /**
     * 题目要求：实现一个函数，该函数接收一个整数n并返回该整数所有的因子组合
     * 举例说明：假如n为32，那么函数将返回[[2, 16],[2, 2, 8],[2, 2, 2, 4],[2, 2, 2, 2, 2],[2, 4, 4],[4, 8]]
     */

    //使用回溯法来解决
    public List<List<Integer>> getFactors(int n){
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(n, new LinkedList<>(), ret);
        return ret;
    }

    //这个方法的作用是：找到数字target的其中一个因子，将该因子放到链表ll中
    private static void backtracking(int target, LinkedList<Integer> ll, List<List<Integer>> ret){
        
        //如果target为1，说明此时ll中元素的乘积就等于题目给的n值
        //也就是说此时我们找到了其中一个结果，因此将这个结果保存到ret中
        if(target == 1){

            //注意，如果此时ll是空集，说明题目给的n值就是1，此时就不应该将这个结果添加到ret中了
            if(!ll.isEmpty())
                ret.add(new ArrayList<>(ll));
            
            return;
        }

        //否则，开始寻找target的所有因子，并将这些因子逐个放到ll链表中；注意：
        //1. 如果ll为空集，说明此时的target就是题目给的n值，此时应该在[2, target / 2]的范围内找target的因子
        //   1.1. 这么做是为了防止最终结果ret出现[1]和[n]元素
        //   1.2. 当然你也可以不这么做，然后在回溯完成后在主函数中自行删除掉ret中的[1]和[n]元素
        //2. 如果ll不为空集，那么为了避免得到重复的因子组合，如[2, 2, 4]和[2, 4, 2]，就需要保证ll中的元素是递增的
        //   2.1. 因此我们需要从ll.peekLast()开始寻找target的因子
        //   2.2. 并且end值取target的值，也就是说，允许target本身作为因子添加到ll中
        int begin = ll.isEmpty() ? 2 : ll.peekLast(), end = ll.isEmpty() ? target / 2 : target;
        
        //在[begin, end]范围内寻找target的因子
        for(int i = begin; i <= end; i++){
            if(target % i != 0)
                continue;
            
            //找到了一个因子i，因此将它添加到ll中，并继续递归调用
            ll.add(i);
            backtracking(target / i, ll, ret);
            
            //回溯
            ll.pollLast();
        }
    }
}