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, do
  - 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]