一尘不染

查找集合的所有子集

algorithm

我需要一种算法来查找集合中元素个数为的集合的所有子集n

S={1,2,3,4...n}

编辑:我无法理解到目前为止提供的答案。我想逐步解释答案如何找到子集。

例如,

S={1,2,3,4,5}

你怎么知道{1}{1,2}是子集?

有人可以用c ++中的一个简单函数来帮助我找到{1,2,3,4,5}的子集


阅读 407

收藏
2020-07-28

共1个答案

一尘不染

递归执行此操作非常简单。基本思想是,对于每个元素,可以将子集划分为包含该元素的子集和不包含子元素的子集,否则这两组子集是相等的。

  • 对于n = 1,子集为{{},{1}}
  • 对于n> 1,找到1,…,n-1的子集,并制作两个副本。对于其中之一,将n添加到每个子集。然后将两个副本合并。

编辑 使其清晰可见:

  • {1}的子集为{{},{1}}
  • 对于{1,2},取{{},{1}},向每个子集加2以获得{{2},{1,2}},并与{{},{1}}进行并集得到{{},{1},{2},{1、2}}
  • 重复直到达到n
2020-07-28