Chương trình đếm tập con không rỗng có tổng min và max nhỏ hơn k bằng Python

Cho danh sách nums và giá trị k. Đếm số tập con không rỗng S sao cho min(S) + max(S) <= k. Tập con là multiset (có thể trùng giá trị do tham chiếu đến phần tử cụ thể).

Ví dụ: nums = [2, 2, 5, 6], k = 7 → 6 (các tập: [2], [2], [2,2], [2,5], [2,5], [2,2,5]).

Quy trình giải quyết (Two Pointers + Powers of 2)

1. Sắp xếp A.
2. Khởi tạo ans = 0, j = N - 1.
3. Với i từ 0 đến N-1:
   • Giảm j cho đến khi A[i] + A[j] <= K.
   • Nếu i <= j và thỏa mãn: ans += 2^(j - i) (số tập con chứa A[i] làm min và max ≤ A[j]).
4. Trả về ans.

Ví dụ mã nguồn

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))  # Output: 6

Đầu vào

[2, 2, 5, 6], 7

Đầu ra

6