我们从用户那里得到非负整数n，并且我们必须打印集合({1,2,3,...,n})的所有子集。(n<=20(
例如，对于n=3，我们必须打印：
{1 , 2 , 3}
{1 , 2}
{1 , 3}
{1}
{2 , 3}
{2}
{3}
{}
,s是可选的，并且可以在不使用任何逗号的情况下打印序列。(类似于｛1 2 3｝(我必须补充一点，子集的顺序必须与示例完全相同。这意味着首先是有1的子集，然后是有2和…的子集。。。。必须首先打印最长的子集。(从最大子集(集合本身(到空集合的词典编纂(
我在互联网上看到很多代码用数组或使用位数组来解决这个问题，这些代码指示我们是否使用数字。问题是，在这个问题中，我们不允许使用任何类型的数组或其他数据结构，如向量等。甚至完全禁止使用字符串之类的数组行为。它只能用递归来解决。
我们也不允许使用任何高级功能。例如，如果我们使用C编写它，则只允许使用stdio.h，或者对于C++，只允许使用<iostream>，而不允许使用其他库。
如果没有任何数组，我不知道如何做到这一点。如何检查必须打印的号码，同时管理{}。
PS1。问题只是在以下条件下的发电机组：
完全禁止使用数组、字符串甚至循环。只是递归。
用户Kosyr用bit运算符提交了一个非常好的答案。因此，如果你想提交另一个答案，请提交一个甚至不使用位运算符的答案。
PS2.
我是在乔治的帮助下写这段代码的，但它不太好用。它没有像12 4这样的东西。它还重复了一些情况。
#include <stdio.h>
void printAllSets (int size)
{printRows (size, 1);}
void printRows (int size , int start)
{
if (start<=size)
{printf( "{ ");
printRow (start, size);
printf ("}");
printf ("n");}
if (start <= size)
{printRows(size -1 , start);
printRows (size , (start + 1));}
}
printRow (int start, int limit)
{
if (start <= limit)
{
printf ("%d ",start);
printRow (start +1, limit);
}
}
int main()
{
printAllSets(5);
printf("{ }");
return 0;
}
PS3.
用户Kosyr用bit运算符提交了一个非常好的答案。因此，如果你想提交另一个答案，请提交一个甚至不使用位运算符的答案。
递归算法非常占用内存。n <= 31的Here算法
#include <iostream>
void bin(unsigned bit, unsigned k, unsigned max_bits) {
if (bit == max_bits) {
std::cout << "{";
bin(bit - 1, k, max_bits);
}
else {
if ((k & (1u << bit)) != 0) {
std::cout << (max_bits - bit) << " ";
}
if (bit != 0) {
bin(bit - 1, k, max_bits);
}
else {
std::cout << "}" << std::endl;
}
}
}
void print(unsigned k, unsigned n, unsigned max_bits) {
bin(max_bits, k, max_bits);
if (k != 0) {
print(k - 1, n, max_bits);
}
}
int main()
{
unsigned n;
std::cin >> n;
print((1u << n) - 1u, 1u<<n, n);
return 0;
}
第一递归print从2^n-1到0枚举k，第二递归bin枚举k的所有位并打印非零位。例如，max_bits = 5和k = 19是10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0，比特4,1,0互操作为集合{5-4,5-1,5-0} => {1,4,5}
循环的替代方法是递归。
为了解决这个问题(我想……还没有测试过(，我通过统计样本日期来研究这个问题，并识别出三种状态，Size、Start和Limit，其进展如下：
Size Start Limit Output
10 1 10 1..10
10 1 9 1..9
... ...
10 1 1 1
10 2 10 2..10
10 2 9 2..9
... ...
10 2 2 2
... ... ...
10 10 10 10
伪代码中的以下递归算法可以做到这一点：
printAllSets size
printRows size 1
printRows size start
print "{"
printRow start size
print "}"
print CRLF
if start <= size
printRows size (start + 1)
printRow start limit
if start <= limit
print start + SPACE
printRow start (limit - 1)
希望这至少能帮你指明正确的方向。
我认为我们可以迭代解决这个问题，我们可以假设它也可以转换为递归，尽管这似乎没有必要。考虑一下，我们可以使用常识，在给定索引的情况下对任何组合进行取消排序。因此，我们所需要做的就是计算我们跳过了多少早期组合，以及在迭代的每个阶段需要取消多少排序(我可能遗漏了以下内容，但我认为总体思路是合理的(：
Skip 0, unrank from `3 choose 3`
`2 choose 2` combinations
{1 , 2 , 3}
Skip 0, unrank from `3 choose 2`
`2 choose 1` combinations
{1 , 2}
{1 , 3}
Skip 0, unrank from `3 choose 1`
`2 choose 0` combinations
{1}
Skip `3 choose 2 - 2 choose 2`,
unrank from `3 choose 2`
`1 choose 1` combinations
{2 , 3}
Skip `3 choose 1 - 2 choose 1`,
unrank from `3 choose 1`
`1 choose 0` combinations
{2}
Skip `3 choose 1 - 1 choose 1`,
unrank from `3 choose 1`
`0 choose 0` combinations
{3}
Empty set
{}
根据定义，集合k，powerset k的幂集是所有可能的集合的集合，包含该给定集合的元素，包括空集本身。显然，当k是空集时，powerset []只是包含空集[ [] ]的集合。现在，给定k、powerset k的幂集，k的幂集加上附加元素E、powerset (K+E)，将包括包含没有E、powerset k的元素的所有可能集，加上除了现在全部包含E之外的那些相同元素
伪代码。。。
let powerset k =
match k with
| [] -> [[]]
| x:xs -> x * powerset xs + powerset xs
或具有尾呼等效性能的
let powerset k =
let (*) e ess = map (es -> e::es) ess
reduce (e ess -> (e * ess) ++ ess) [ [] ] (reverse k)
(在F#中(
let rec powerset k =
match k with
| [] -> [ [] ]
| x::xs ->
let withoutE = powerset xs
let withE = List.map (fun es -> x::es) withoutE
List.append withE withoutE
或者更简洁的
let rec powerset = function
| [] -> [ [] ]
| x::xs -> List.append (List.map (fun es -> x::es) (powerset xs)) (powerset xs)
一个更好的版本将允许尾部调用优化。。。这是我们使用常见的功能模式实现的：
let rec powerset2 k =
let inline (++) a b = List.concat [a;b]
let inline (+*) a bs = List.map (fun b -> a::b) bs
List.fold
(fun ac a -> (a +* ac) ++ ac)
[ [] ]
(List.rev k)
--这一切我花了一段时间才重新发现。这是一个有趣的小谜题