（用二进制的思路）给定一个集合S，打印出集合所有的子集

87 阅读 0 评论 58 点赞

我是靠谱客的博主自觉大叔，最近开发中收集的这篇文章主要介绍（用二进制的思路）给定一个集合S，打印出集合所有的子集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二进制即0，1的组合，我们可以用0，1来分别表示集合的某一个元素到底存不存在一个集合中。

例如：假设S={“A”,"B","C"}

111(7)->A B C

110(6)->A B

101(5)->A C

100(4)->A

011(3)->B C

010(2)->B

001(1)->C

000(0)->NULL

代码实现如下：

package lintcode;

public class HandleAllSubSet {
	public void handleAllSubSet(String[] set){
		int len = set.length;
		int val =0;
		//根据字符串的长度，产生跟长度相同的二进制数   比如 长度是3，则val=111=7
		for(int i = 0 ;i<len;i++)
		{
			val |= (1<<i);
		}
		
		while(val>0){
			printSetByBinary(val,set);
			val--;
		}
	}
	/**
	 * 根据二进制位的描述输出想象的子集 例如 val=1 set = {"c"}
	 * @param val
	 * @param set
	 */
	public void printSetByBinary(int val,String[] set){
		String binary = remedyBinaryString(val,set.length);
		int idx = 0;
		boolean isNull = true;
		
		while(idx<binary.length()){
			if(binary.charAt(idx)=='1'){
				if(isNull == false){
					System.out.print(",");
				}
				System.out.print(set[idx]);
				isNull = false;
			}
			idx++;
		}
		if(isNull){
			System.out.println("null");
		}
		System.out.println();
	}
	/**
	 * 根据传入的val与字符串的长度，来构造响应长度的其余的字符串子集 例如 如果val=101，而字符串有四个则填充为0101
	 * @param val
	 * @param strLen
	 * @return
	 */
	public String remedyBinaryString(int val,int strLen){
		String binary = Integer.toBinaryString(val);
		while(binary.length()<strLen){
			binary = "0"+binary;
		}
		return binary;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HandleAllSubSet h  =new HandleAllSubSet();
		String[] set ={"A","B","C","D","E"};
		h.handleAllSubSet(set);

	}

}