9.9遞歸和動态規劃（四）——傳回某集合的全部子集

三種方法： 方法一：疊代

//疊代
	/**
	 * 注意：每次增加集合後會改變原來的集合，無法繼續從集合中取出元素。
           

* 必須通過一個中間參數moreSubsets來儲存中間結果，最後增加allSubsets。

* @author Lynne * @param set * @param index * @return */ public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set,int index){ ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>(); allSubsets.add(new ArrayList<Integer> ());//增加空集合 while(index<set.size()){ int item=set.get(index); ArrayList<ArrayList<Integer>> moreSubsets=new ArrayList<ArrayList<Integer>>(); for(ArrayList<Integer> subsets:allSubsets){ ArrayList<Integer> newSubsets=new ArrayList<Integer>(); newSubsets.addAll(subsets); newSubsets.add(item); moreSubsets.add(newSubsets); } allSubsets.addAll(moreSubsets); index++; } return allSubsets; }

方法二：遞歸

//遞歸法
	/**
	 * 思路：簡單構造法
	 * 		計算P（n-1），複制一份結果，然後在每一個複制後的集合中增加an。
           

* @param set * @param index * @return */ public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set,int index){ ArrayList<ArrayList<Integer>> allSubsets; if(set.size()==index){//終止條件。增加空集合 allSubsets=new ArrayList<ArrayList<Integer>>(); allSubsets.add(new ArrayList<Integer>());//空集合 }else{ allSubsets=getSubsets(set, index+1); int item=set.get(index); ArrayList<ArrayList<Integer>> moreSubsets=new ArrayList<ArrayList<Integer>>(); for(ArrayList<Integer> subsets:allSubsets){ ArrayList<Integer> newSubsets=new ArrayList<Integer>(); newSubsets.addAll(subsets); newSubsets.add(item); moreSubsets.add(newSubsets); } allSubsets.addAll(moreSubsets); } return allSubsets; }

方法三：組合數學

//組合數學
	/**
	 * 思路：疊代訪問1到2^n的全部數字，再轉化為集合
	 * 每一個元素有兩個選擇:1)在集合中（“yes”）;2)不在集合中（“no”）。
           

即每一個子集都是一串yes和no。

* 總共同擁有2^n個子集，将每一個yes看做1，每一個no看做0，即能夠表示為一個二進制串。

* 是以。構造全部的子集就等同于構造全部的二進制數。疊代訪問1到2^n的全部數字。再轉化為集合。

* @param set * @return */ public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set){ ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>(); int size=1<<set.size();//集合的子集個數。計算2^n。

for(int i=0;i<size;i++){ ArrayList<Integer> subsets=new ArrayList<Integer>(); subsets=convertIntToSet(i); allSubsets.add(subsets); } return allSubsets; } public static ArrayList<Integer> convertIntToSet(int x){ ArrayList<Integer> subsets=new ArrayList<Integer>(); for(int i=x;i>=1;i>>=1){ if((i&1)==1) subsets.add(i); } return subsets; }

轉載于:https://www.cnblogs.com/yfceshi/p/7086572.html