โปรแกรมนับเซตย่อยไม่ว่างที่ผลรวม min และ max น้อยกว่า k ใน Python

สมมติว่าเรามีรายการ nums และค่า k หาจำนวนเซตย่อยไม่ว่าง S ที่ min(S) + max(S) <= k เซตย่อยเป็น multiset (มีค่าซ้ำได้ เพราะอ้างอิง index ไม่ใช่ค่า)

ตัวอย่าง: nums = [2, 2, 5, 6], k = 7 ผลลัพธ์ 6 เซตย่อยคือ [2], [2], [2,2], [2,5], [2,5], [2,2,5]

ขั้นตอนการแก้ปัญหา (Two Pointers + Combinatorics)

1. N = len(A), เรียง A
2. ans = 0, j = N - 1
3. วนลูป i จาก 0 ถึง N-1:
   • วนลูป while j > 0 และ A[i] + A[j] > K: j -= 1
   • ถ้า i <= j และ A[i] + A[j] <= K:
     • ans += 2^(j - i) (จำนวนเซตย่อยที่เลือกได้จากช่วง i ถึง j)
4. คืนค่า ans

ตัวอย่างโค้ด 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)  # 2^(j-i)
        return ans

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

อินพุต / เอาต์พุต

Input: [2, 2, 5, 6], 7

Output: 6