再帰的Javaプログラムの基底を決定する

Question

このコードは、一連の数値のpowersetを生成します。例えば、（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（）ですか？

Answer 1

再帰的コードは、ゼロから始まるinputSetリストへの有効なインデックスを1つずつ順番に実行します。現在の呼び出しでは、inputSetのインデックスとしてtoBeSelectedが使用され、次のレベルの呼び出しにはtoBeSelected+1が渡されます。

したがって、基本ケースの意味は、toBeSelectedが無効になったときに起こる、それ以外のものは選択されないということです。

toBeSelectedの最後の有効な値はinputSet.size()-1です。 toBeSelected==inputSet.size()は、最初の無効値toBeSelectedを検出し、再帰の基本ケースとして機能します。

Answer 2

n要素セットのパワーセットを構築しようとしているので、0要素空集合から始めて1要素セットに移動し、次に2要素セットに移動するなどです。

これはいつ終了する必要がありますか？最後に、n要素を設定しようとしているとき、要素が1つしかないため、入力自体が設定されているためです。