此代码生成一组数字的幂集。例如,如果我们有 (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
的第一个无效值,作为递归的基本情况。
关于java - 确定递归 java 程序的基本情况,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45653249/