Pythonでセットの最小要素と最大要素の合計がk未満である空でないサブセットをカウントするプログラム

numsと呼ばれる数のリストと別の値kがあるとすると、Sの最小値+Sの最大値<=kとなるような空でないサブセットSの数を見つける必要があります。サブセットはマルチセットであることに注意する必要があります。したがって、サブセットは値ではなくリストの特定の要素を参照しているため、サブセットに重複する値が存在する可能性があります。

したがって、入力がnums =[2、2、5、6]、k =7の場合、出力は6になります。これは、[2]、[2]、[2、 2]、[2、5]、[2、5]、[2、2、5]。

これを解決するには、次の手順に従います-

• N：=Aのサイズ
• リストAを並べ替える
• ans：=0
• j：=N-1
• 0からNの範囲のiについては、
  • jおよびA[i]+ A [j]> Kの場合、実行
    • j：=j-1
  • i<=jかつA[i]+ A [j] <=Kの場合、
    • ans：=ans + 2 ^（j --i）
• 回答を返す

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

例

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