冪集合

問題

ある集合の全ての部分集合を返す

考え方

再帰的に考える。 N-1この要素の全ての部分集合がわかっているときに、次の部分集合はどうなるか？ N個目の要素を加えたsubsetsを元のsubsetsに加えれば良い。 f(n) = f(n-1) + {f(n-1), set[n]}

コード例

def allset(lists):
    # setをlistで与える。
    if len(lists) == 1:
        return [set(), {lists[0]}]
    ans = allset(lists[:-1])
    for _ in allset(lists[:-1]):
        _.add(lists[-1])
        ans.append(_)
    return ans


if __name__ == "__main__":
    lists =  [1, 2, 3, 4]
    print(allset(lists))

参考

問題は 世界で闘うプログラミング力を鍛える本 | マイナビブックス から