Python의 주어진 요소 세트에서 주어진 합계를 얻을 수 있는지 확인하십시오.

num이라는 배열과 다른 값 합계가 있다고 가정합니다. nums에 있는 요소를 추가하여 합계를 얻을 수 있는지 확인해야 합니다. 단일 요소를 여러 번 선택할 수 있습니다.

따라서 입력이 nums =[2, 3, 5] sum =28과 같으면 5 + 5 + 5 + 5 + 3 + 3 + 2를 사용하여 26을 얻을 수 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 최대 :=1000
• table :=0으로 채워진 MAX 광고 크기의 배열
• util() 함수를 정의합니다. 시간이 많이 걸립니다
• 테이블[0] :=1
• 목록 번호 정렬
• 0부터 숫자 - 1까지의 범위에 있는 i에 대해
  • val :=nums[i]
  • 테이블[val]이 0이 아니면
    • 다음 반복으로 이동
  • 0 ~ MAX - val - 1 범위의 j에 대해
    • 테이블[j]가 0이 아니면
      • 테이블[j + val] :=1
• 메인 방법에서 다음을 수행하십시오 -
• 유틸(숫자)
• 테이블[sum]이 0이 아니면
  • 참 반환
• 거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

MAX = 1000
table = [0] * MAX
def util(nums):
   table[0] = 1
   nums.sort()
   for i in range(len(nums)):
      val = nums[i]
      if table[val]:
         continue
      for j in range(MAX - val):
         if table[j]:
            table[j + val] = 1
def solve(nums, sum):
   util(nums)
   if table[sum]:
      return True
   return False
nums = [2, 3, 5]
sum = 28
print (solve(nums, sum))

입력

[2, 3, 5], 28

출력

True