LintCode第652题-递归版

描述

一个非负数可以被视为其因数的乘积。编写一个函数来返回整数 n 的因数所有可能组合。

组合中的元素(a1,a2,...,ak)必须是非降序。(即，a1≤a2≤...≤ak)。

结果集中不能包含重复的组合。

样例1

输入：8
输出： [[2,2,2],[2,4]]
解释： 8 = 2 x 2 x 2 = 2 x 4

样例2

输入：1 
输出： []

思路:

易错点:

1.容易忽略掉回溯语句,回溯后没清除path,会导致组合路径出错

pathList.remove(pathList.size()-1)  

 2. dfs(1,supplementNum,pathList,totalList);该方法里面是supplementNum而不是startFactor

如果是传入的是startFactor会有无线递归的风险

代码如下:

import java.util.*;

public class Solution {

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

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

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

        dfs(n,2,pathList,totalList);

        return totalList;

    }

    void dfs(int supplementNum ,int startFactor,List<Integer> pathList,List<List<Integer>> totalList)

    {

        if(supplementNum==1)

        {

            if(pathList.size()>1)

            {

                totalList.add(new ArrayList<>(pathList));

            }

            return;

        }

        for(int factor=startFactor;factor<=Math.sqrt(supplementNum);factor++)

        {

            if(supplementNum%factor==0)

            {

                pathList.add(factor);

                dfs(supplementNum/factor,factor,pathList,totalList);

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

            }

        }

        if(supplementNum>=startFactor)

        {

            pathList.add(supplementNum);

            dfs(1,supplementNum,pathList,totalList);

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

        }

    }

   

    }