Subsets
異なる整数のリスト nums が与えられます。空の部分集合とリスト全体を含む、すべての部分集合を返してください。つまり、n 個の値からは 2^n 個の部分集合が得られます。各部分集合の値は昇順に並べ、部分集合は辞書順に並べてください。2つの部分集合を値ごとに比較し、最初に異なる値で順序を決めます。一方の部分集合がもう一方の先頭部分と一致する場合は、短い方を先にします。[1, 2] の場合、答えは [[], [1], [1, 2], [2]] です。
関数
- numsinteger-array
- 値はすべて異なり、順序は任意
- 戻り値integer-2d-array
- すべての部分集合をそれぞれ昇順に並べ、辞書順で列挙
制約
1 ≤ nums.length ≤ 10-10 ≤ nums[i] ≤ 10- すべての
numsの値は異なります。 numsはどのような順序で現れてもかまいません。
例
- 入力
- nums = [3, 1, 2]
- 出力
- [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
- 説明
- 並べ替えると、値は 1、2、3 で、3つの値からは 2^3 = 8 個の部分集合ができます。
[1, 2]は[1, 2, 3]より前に来ます。これは前者が後者の先頭部分だからです。また、2番目の位置では 2 が 3 より小さいため、[1, 2, 3]は[1, 3]より前に来ます。
- 入力
- nums = [0]
- 出力
- [[], [0]]
- 説明
- 1つの値には2つの部分集合があります。値を含めずに
[]を得るか、値を含めて[0]を得ます。空集合が常に先に来ます。
- 入力
- nums = [5, -2]
- 出力
- [[], [-2], [-2, 5], [5]]
- 説明
- 値は -2 と 5 の順に並ぶので、
[-2, 5]はその順序で書きます。-2 を含むすべての部分集合は、-2 が 5 より小さいため、[5]より前に来ます。
提出時に隠しテスト+13件
発展問題
再帰を使わずに、直前の部分集合からそれぞれを直接作って、同じリストを生成できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
部分集合では、各値の行き先は2つ、つまり含まれるか含まれないかです。
n個の値のリストには部分集合がいくつあり、それぞれをより小さな部分集合からどのように作れるでしょうか？まず値を並べ替えます。最後に追加した値より右にある値だけを追加すれば、すべての部分集合は昇順に作られ、同じ部分集合が二度作られることはありません。
開始インデックスを受け取る再帰的なヘルパーを作成します。現在のパスを部分集合として記録し、その後、開始位置から末尾までの各インデックスについて、その値を追加して次のインデックスから再帰し、再びその値を削除します。ループの前、処理に入るときに記録することで、ソートしなくても部分集合が辞書順に並びます。
解説
部分集合は 2^n 個あるため、どの方法でも O(2^n) 未満の処理では済みません。本当の問題は、1024 個のリストを後から並べ替えることなく、必要な順序で各部分集合を一度ずつ生成する方法です。ソート済みの値を対象にバックトラッキングし、決定木の各ノードに入るたびに記録すれば、部分集合を辞書順どおりに巡回できます。
ビットマスク、その後にソート
考え方
ソート済みの値を位置 0 から n-1 に並べます。部分集合は各位置を含むか含まないかを表し、それが数値の n ビットで表されます。したがって、0 から 2^n-1 までの数値が部分集合に対応します。たとえば [1, 2, 3] の場合、マスク 5 は2進数で 101 なので、ビット 0 と 2 が立っており、[1, 3] を表します。マスク 0 は空の部分集合、マスク 7 はリスト全体です。
異なるマスクは異なる部分集合を表し、すべての部分集合にマスクがあるため、このループは 2^n 個の部分集合をそれぞれ一度ずつ生成します。ソート済みの値に対して位置 0 から順にビットを読み取ると、各部分集合は昇順で出力されます。
マスクは問題で求められる順序では出力されません。マスク 1 は [1]、マスク 2 は [2]、マスク 3 は [1, 2] なので、[2] が [1, 2] より前に来てしまいます。これを修正するには、値を一つずつ比較し、接頭部分列を先にする比較関数を使ってソートします。ソートには生成よりも多くのコストがかかります。2^n 個の部分集合にはおよそ n × 2^n 回の比較が必要で、各比較では最大 n 個の値を読み取ります。n = 10 の場合、読み取り回数は約 10^5 回で、まだ高速ですが、次の方法では発生しない処理です。
アルゴリズム
numsをソートし、すべての部分集合が昇順になるようにします。- 0 から 2^n-1 までのすべてのマスクについて、ビットがセットされている位置の値を集めます。
- 部分集合のリストをソートします。2つの部分集合が異なる最初の位置では、小さい値を優先し、一方が先に尽きた場合は、その部分集合を先にします。
- ソート済みのリストを返します。
def subsets(nums):
values = sorted(nums)
n = len(values)
result = []
for mask in range(1 << n):
# Bit i of mask says whether values[i] is in this subset.
result.append([values[i] for i in range(n) if (mask >> i) & 1])
# Python compares lists position by position, and a prefix comes first.
result.sort()
return resultバックトラッキング：選択し、探索し、選択を取り消す
考え方
部分集合を木としてイメージしてください。根は空の部分集合です。あるノードの下には、最後に追加した値より大きい値を追加できます。値をソートした [1, 2, 3] の場合、根には子として [1]、[2]、[3] があります。[1] には子として [1, 2] と [1, 3] があり、[1, 2] には子として [1, 2, 3] があります。昇順で書く方法は一通りしかないため、各部分集合はこの木にちょうど一度だけ現れます。また、葉だけでなく、すべてのノードが答えになります。
バックトラッキングでは、共有リスト path を使って木をたどります。子へ進むには 選択 します。値を追加します。次に 探索 します。再帰呼び出しを行い、ヘルパー関数は到着した時点で path のコピーを記録します。そして 選択を取り消し ます。値を削除することで、path を親の状態に戻し、次の兄弟を試せるようにします。入るときにすべてのノードを記録するため、親は常に子より先に出力されます。
これが、ソートしなくても出力が辞書順になる理由です。各ノードの子は小さい値から順に試され、探索は次の枝へ進む前に現在の枝全体をたどります。[1, 2, 3] の場合、[]、[1]、[1, 2]、[1, 2, 3]、[1, 3]、[2]、[2, 3]、[3] の順に記録されます。これは、接頭辞がその拡張形より先に来る辞書の順序です。
木には 2^n 個のノードがあり、パスのコピーには最大 n のコストがかかるため、時間計算量は O(n × 2^n) で、答え自体のサイズに相当します。出力のほかに、パスと呼び出しスタックを保持しますが、どちらも深さは最大 n です。
アルゴリズム
- 値を並べ替えます。
explore(start)を記述します。最初に、pathのコピーを結果に追加します。- 次に、
startから末尾までの各インデックスiについて、values[i]をpathに追加し（選択）、explore(i+1)を呼び出し（探索）、最後の値を削除します（選択を取り消す）。 - 空の path で
explore(0)を呼び出し、結果を返します。
def subsets(nums):
values = sorted(nums)
result = []
path = []
def explore(start):
# Every node of the decision tree is a subset: record it on the way in.
result.append(path[:])
for i in range(start, len(values)):
path.append(values[i]) # choose
explore(i + 1) # explore: only larger values may follow
path.pop() # un-choose
explore(0)
return result
落とし穴と境界ケース
ここでの誤答の多くは、順序やリストの共有が原因です。
- コピーではなく
path自体を追加してしまう。すると、すべての要素が同じリストを参照し、探索が終わるとそのリストは空になるため、[]が2^n個返されます。 numsをソートし忘れる。[3, 1, 2]の場合、木は[3, 1]を構築しますが、これは昇順ではないため、探索順は辞書順ではなくなります。- 順列の場合のように、葉でのみ記録する。この木のすべてのノードが部分集合なので、最後まで到達したパスだけを記録すると、部分集合の数が足りません。
i+1ではなくstart+1で再帰する。すると、ある値の後にそれより大きい値や、さらには同じ値が続くことがあり、[3, 2]や[3, 3]のような、昇順ではない部分集合が得られます。- 包含・除外の木（値0、次に値1、という順に判断する方法）を使い、葉を記録する。すべての2^n個の部分集合は見つかりますが、包含を先に試すと全要素のリストが最初になり、除外を先に試すと
[3]が[2]より前になります。どちらも辞書順ではありません。 - 長さを優先してソートする比較関数を使うと、
[]、[1]、[2]、[3]、[1, 2]の順になり、これは異なる順序です。
よくある質問4
n 個の要素を持つ集合は、部分集合をいくつ持ちますか？
2^n。各要素は他の要素とは独立して、含めるか含めないかのどちらかなので、選択肢の数を掛け合わせます。最初の要素に2通り、2番目の要素に2通り、というように続きます。値が3つの場合は部分集合が8個、10個の場合は1024個になります。空集合と集合全体も数に含まれます。
部分集合問題の時間計算量は何ですか？
O(n × 2^n)。部分集合は2^n個あり、それぞれを書き出すのに最大nステップかかるため、答えを返すだけでもこれだけの計算量が必要です。バックトラッキングはこの計算量を達成し、追加の領域はO(n)だけです。ビットマスクを使った生成も同じ速さですが、その後で結果をソートすると、さらにn倍の計算量が加わります。
部分集合にはバックトラッキングとビットマスクのどちらを使うべきですか？
ビットマスクは短く、再帰が不要で、含めるか除外するかの選択をビットで可視化できます。バックトラッキングでは、部分集合がそのまま辞書順で得られ、よくあるバリエーションにも対応できます。たとえば、重複する値をスキップする、サイズが k の部分集合だけにする、または目標の合計に達する部分集合だけにする、といった場合には、探索の分岐を早い段階で打ち切ることができます。
Subsets で重複する値をどのように扱いますか？
値をソートし、バックトラッキング用ヘルパーのループ内で、同じ階層で直前の値と等しい値をスキップします。条件は i > start と values[i] == values[i-1] です。最初のコピーですでにそれを使うすべての部分集合を探索しているため、2つ目のコピーから始まる兄弟分岐では、同じ部分集合を再び構築するだけです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def subsets(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 1, 2]
期待値
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]