【Python】最小値と最大値の合計がk以下になる空でない部分集合の個数を数える方法

問題の概要

数値のリスト nums ともうひとつの値 k が与えられたとき、「min(S) + max(S) ≤ k」を満たす空でない部分集合 S の個数を求めます。ここで重要なのは、部分集合がマルチセット（重複を許す集合）として扱われる点です。部分集合はリスト内の「値」そのものではなく「特定の位置にある要素」を参照するため、同じ値の要素が複数あっても、それらは互いに異なる部分集合としてカウントされます。

たとえば、入力が nums = [2, 2, 5, 6]、k = 7 の場合、出力は 6 になります。条件を満たす部分集合は、[2]、[2]、[2, 2]、[2, 5]、[2, 5]、[2, 2, 5] の6つです。

解き方の手順

この問題は、リストをソートした上で二つのポインタ（インデックス）を使う二ポインタ法で効率よく解けます。手順は以下のとおりです。

• N := リスト A のサイズとする
• リスト A をソートする
• ans := 0（答えを保持する変数）
• j := N − 1 とする
• i を 0 から N−1 まで動かしながら、以下を繰り返す
  • A[i] + A[j] > K である間、j を 1 ずつ減らす
  • i ≤ j かつ A[i] + A[j] ≤ K ならば、ans に 2^{(j − i)} を加算する
• 最後に ans を返す

このアルゴリズムが正しく動作する理由

ソート済みのリストでは、インデックス i の要素 A[i] を部分集合の最小値として固定できます。A[i] + A[j] ≤ K を満たす最大の j が分かれば、インデックス i+1 から j までの各要素については「部分集合に含めるか含めないか」を自由に選べます。各要素に2通りの選択肢があるため、合計 2^{(j − i)} 個の部分集合が得られます。最小値の位置ごとに数えることで、同じ部分集合が二重にカウントされる心配もありません。

Pythonでの実装例

理解を深めるために、次の実装例を見てみましょう。

class Solution:
   def solve(self, A, K):
      N = len(A)
      A.sort()
      ans = 0
      j = N - 1
      for i in range(N):
         while j and A[i] + A[j] > K:
            j -= 1
         if i <= j and A[i] + A[j] <= K:
            ans += 1 << (j - i)
      return ans

ob = Solution()
nums = [2, 2, 5, 6]
k = 7
print(ob.solve(nums, k))

入力

[2, 2, 5, 6]

出力

6

計算量の目安

ソートに O(n log n)、その後の二ポインタによる走査は各インデックスが高々一度ずつ処理されるだけなので O(n) です。全体の時間計算量は O(n log n) となり、すべての部分集合を列挙する O(2ⁿ) のアプローチと比べても大幅に効率的であることが分かります。