Python에서 세 가지 작업으로 배열 합계를 K로 만들 수 있는지 확인하십시오.

nums라는 숫자 목록과 양수 값 K가 있다고 가정합니다. nums −

• 하나의 숫자를 음수로 만듭니다.
• 숫자의 인덱스(색인 1부터 시작)를 숫자 자체에 추가
• 숫자 자체에서 숫자 인덱스를 뺍니다.

마지막으로 이러한 연산을 각 요소에 대해 한 번만 수행하여 주어진 배열이 배열의 합이 k가 될 때 변환될 수 있는지 확인해야 합니다.

따라서 입력이 nums =[1,2,3,7] k =8과 같으면 2와 3에서 인덱스 2와 3을 빼서 [1, 0, 0, 7]이므로 이제 합은 8 =k입니다.

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

• 크기 :=100
• is_ok() 함수를 정의합니다. 이것은 i, total, k, nums, table이 필요합니다.
• n :=숫자 크기
• 총 <=0이면
  • 거짓을 반환
• i>=n이면
  • 합계가 k와 같으면
    • 참 반환
• 거짓을 반환
• 테이블[i, total]이 -1이 아니면
  • 반환 테이블[i, total]
• table[i, total] :=1 (is_ok(i+1, total - 2 * nums[i], k, nums, table)이 0이 아니거나 is_ok(i+1, total, k, nums, table)은 0이 아님), 그렇지 않으면 0
• table[i, total] :=(is_ok(i+1, total -(i+1) , k, nums, table) 또는 table[i, total])일 때 1, 그렇지 않으면 0
• table[i, total] :=(is_ok(i+1, total + i + 1, k, nums, table) 또는 table[i, total])일 때 1, 그렇지 않으면 0
• 반환 테이블[i, total]
• 메인 방법에서 다음을 수행하십시오 -
• total :=nums에 있는 모든 요소의 합계
• table :=크기와 길이가 같고 -1로 채워지는 배열
• 0~크기 범위의 i에 대해
  • table[i] :=크기와 길이가 같고 -1로 채우는 배열
• return is_ok(0, total, k, nums, table)

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

예시

size = 100
def is_ok(i, total, k, nums, table):
   n = len(nums)
   if total <= 0:
      return False
   if i >= n:
      if total == k:
         return True
      return False
   if table[i][total] != -1:
      return table[i][total]
   table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
   table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total] table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
   return table[i][total]
def solve(nums, k):
   total = sum(nums)
   table = [-1]*size
   for i in range(size):
      table[i] = [-1]*size
   return is_ok(0, total, k, nums, table)
nums = [1,2,3,7]
k = 8
print(solve(nums, k))

입력

[1,2,3,7], 8

출력

True