讨论/题目交流/集合求子集/
集合求子集

[问题描述]
给定一个集合A,求A的所有非空子集。例如A={a,b}时,则它的所有非空子集为{a},{b},{a,b}。集合A不空,并且A的元素个数不超过10个。
[输入]
有多组测试数据,每组测试数据为一行。
每行表示一个集合,集合由一对大括号括起来,集合之间的元素用一个逗号隔开。之间没有任何的空白字符。已经知道集合元素按字典顺序排列。
[输出]
每组测试数据输出为2^n-1行,每行表示一个非空子集。子集与子集的顺序参考输出样列。(对应的二进制由小到大)
每个子集的元素按字典顺序排列,元素之间用逗号隔开,没有任何的空白字符。子集由一对大括号括起来。
[输入样列]
{a,b,c}
[输出样例]
{a}
{b}
{a,b}
{c}
{a,c}
{b,c}
{a,b,c}

展开讨论
qbz95发起于 2020-03-18

可以这么做:
对于输入的集合,每个集合从0~n进行编号,输出的行从1~2^N-1进行编号,第n个元素会出现的行号N一定满足:
N & 2^n != 0
即,如果n=0,则N=1,3,5,7,9...,如果n=1,则N=2,3,6,7,10,11...,
因为n的最大数为10,因此,可以将n和N的列表的对应关系做成一个字典或者List的数组。
然后遍历每个n的时候遍历字典,将元素添加到对应行的末尾即可。

1
展开全部 3 讨论