アルゴリズム 体操24 Subsets

Subsets

個別の要素を持つセットを指定して、その個別のサブセットをすべて見つけます。

例

Input: [1, 3]
Output: [], [1], [3], [1,3]

Input: [1, 5, 3]
Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

Solution

指定されたセットのすべてのサブセットを生成するには、幅優先探索（BFS）アプローチを使用できます。空のセットから始め、すべての数値を1つずつ繰り返し、それらを既存のセットに追加して新しいサブセットを作成できます。

例題として、[1, 5, 3]を考えてみます。

1. 空のセットから始めます：[[]]
2. 既存のすべてのサブセットに最初の番号（1）を追加して、新しいサブセットを作成します。[[],[1]]
3. 既存のすべてのサブセットに2番目の数値（5）を追加します：[[],[1],[5],[1,5]]
4. 3番目の数値（3）を既存のすべてのサブセットに追加します：[[],[1],[5],[1,5],[3],[1,3],[5,3],[1,5,3]]

イメージ図

実装

# Time Complexity: O(2^N) where N is the total number of elements in the input set
# Space Complexity: O(2^N)
def find_subsets(nums):
  subsets = []
  # start by adding the empty subset
  subsets.append([])
  for currentNumber in nums:
    # we will take all existing subsets and insert the current number in them to create new subsets
    n = len(subsets)
    for i in range(n):
      # create a new subset from the existing subset and insert the current element to it
      subset = list(subsets[i])
      subset.append(currentNumber)
      subsets.append(subset)

  return subsets


def main():

  print("Here is the list of subsets: " + str(find_subsets([1, 3])))
  print("Here is the list of subsets: " + str(find_subsets([1, 5, 3])))


main()