有如下问题: 输入一个任意正整数n,由小于该整数的所有非负整数构成的一个数列{0,1,2,3,n-1},要求输出该数列的所有子集。例如:输入3即要输出:{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}请指点,谢谢!
回朔可以吧,效率很低.a[i]=1;表示i被选中.a[i]=0表示i没有被选种.void Backtract(int t){ if(t>n) { 判断输出a[i]中为1的i. } for(int i=0;i<n;i++) { a[t]=i; if(当前i与前面被选中要大) Backtract(t+1); }}
斑竹的算法我有点晕:)此题为应聘软件工程师的一道笔试题,我把它列出来,请大家多出出主意,有没有更好的容易理解的算法/
列出所有子集的方法有很多下边介绍一种用二进制对应关系列出所有字集的方法:拿{1,2,3}为例{} 对应000 //0表示不在集合中,1表示在{1} 对应100{2} 010{3} 001{1,2} 110{1,3} 101{2,3} 011{1,2,3} 111所以{1,2,3}的所有字集与3位二进制数是对应的.也即产生二进制数,就可以产生所有字集.
2^n 就是 1<<n