java - 确定递归Java程序的基本情况

此代码生成一组数字的幂集。例如，如果我们有（0,1,2），则幂集为{{0,1,2），（0,2），（1,2），（0,1），（2），（1） ，（0），（）}

public static List<List<Integer>> generatePowerSet(List<Integer> inputSet){
    List<List<Integer>> powerSet = new ArrayList<>();
    directedPowerSet(inputSet,0,new ArrayList<Integer>(), powerSet);
    return powerSet;
}
public static void directedPowerSet(List<Integer> inputSet, int toBeSelected, List<Integer> selectedSoFar,List<List<Integer>> powerSet){
    if(toBeSelected == inputSet.size()){
        powerSet.add(new ArrayList<Integer>(selectedSoFar));
        return;
    }
    //Generate all subsets that contain inputSet[toBeSelected].
    selectedSoFar.add(inputSet.get(toBeSelected));
    directedPowerSet(inputSet,toBeSelected+1,selectedSoFar,powerSet);
    //Generate all subsets that do not contain inputSet[toBeSelected].
    selectedSoFar.remove(selectedSoFar.size()-1);
    directedPowerSet(inputSet,toBeSelected+1,selectedSoFar,powerSet);
}

为什么当toBeSelected == inputSet.size（）时是基本情况？

最佳答案

递归代码从零开始，将有效索引逐一地遍历inputSet列表。当前调用使用toBeSelected作为inputSet的索引，并将toBeSelected+1传递到下一级的调用。

因此，基本情况的含义是没有其他选择，这在toBeSelected变为无效时发生。

toBeSelected的最后一个有效值为inputSet.size()-1; toBeSelected==inputSet.size()检测到toBeSelected的第一个无效值，作为递归的基本情况。