Chương trình đếm các tập hợp con không rỗng trong đó tổng phần tử tối thiểu và tối đa của tập nhỏ hơn k trong Python

Giả sử chúng ta có một danh sách các số gọi là num và một giá trị khác k, chúng ta phải tìm số lượng các tập con S khác rỗng sao cho min của S + max của S <=k. Chúng ta phải ghi nhớ rằng các tập con là nhiều tập. Vì vậy, có thể có các giá trị trùng lặp trong các tập hợp con vì chúng tham chiếu đến các phần tử cụ thể của danh sách, không phải giá trị.

Vì vậy, nếu đầu vào là nums =[2, 2, 5, 6], k =7, thì đầu ra sẽ là 6, vì chúng ta có thể tạo các tập con sau như:[2], [2], [2, 2], [2, 5], [2, 5], [2, 2, 5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=kích thước của A
• sắp xếp danh sách A
• ans:=0
• j:=N - 1
• đối với tôi trong phạm vi từ 0 đến N, thực hiện
  • while j và A [i] + A [j]> K, thực hiện
    • j:=j - 1
  • nếu tôi <=j và A [i] + A [j] <=K, thì
    • ans:=ans + 2 ^ (j - i)
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[2, 2, 5, 6]

Đầu ra

6