By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

打印一个集合所有的子集和，比如{a,b,c}的子集和有{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}以及 空

解析

一个元素个数为n的集合所包含的所有组合的子集个数有2^n个，这样其实就可以将所以集合的情况映射到0~2^n-1个，然后按位取元素即可

比如{a,b,c}这个三元素的集合按位映射
{0,0,0}=>空
{0,0,1}=>{c}
{0,1,0}=>{b}
{0,1,1}=>{b,c}
.
.
.
{1,1,1}=>{a,b,c}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 将集合映射到位，然后进行与操作,然后一个集合可能含有的子元素最多是2^n个
 * @param cs
 */
public static void subCollection(char[] cs)
{
	int len=cs.length,maxNum=1<<len;
	int temp=0;
	int mark=0x1;
	
	for(int i=0;i<maxNum;i++)
	{
		temp=i;
		for(int j=0;j<len && temp!=0;j++)
		{
			if((temp&mark)==1)//取最低位的数字是否为1   
			{
				System.out.print(cs[j]);
			}
			temp=temp>>1;//右移一位
		}
		System.out.println("");
	}
	
}

最终的复杂度为O(n*2^n)，最主要的是这种方式代码写起来很方便
其测试代码为：

1
2
3
4
public static void main(String[] args) {
	char[] cs={'a','b','c'};
	subCollection(cs);
}

输出的结果为

a
b
ab
c
ac
bc
abc

参考

July微软100道面试题 忘了第哪一道 -_-

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考