Advertisement
turegum

Untitled

Feb 11th, 2024 (edited)
721
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.18 KB | Source Code | 0 0
  1. import sys
  2.  
  3. f = sys.stdin
  4.  
  5. line =  f.readline().split()
  6. n = int(line[0])
  7. s = float(line[1])
  8. a = [float(x) for x in f.readline().split()]
  9.  
  10. def generate_subsets_sums(numbers):
  11.     subset_sums = {0}
  12.     for number in numbers:
  13.         new_sums = set()
  14.         for existing_sum in subset_sums:
  15.             new_sums.add(existing_sum + number)
  16.         subset_sums.update(new_sums)
  17.     return subset_sums
  18.  
  19. def is_subset_sum_possible(numbers, target_sum, tolerance=1e-6):
  20.     # Делим на 2 части
  21.     mid = len(numbers) // 2
  22.     left_half, right_half = numbers[:mid], numbers[mid:]
  23.  
  24.     # Генерируем все подмножества сумм для левой и правой частей
  25.     left_sums = generate_subsets_sums(left_half)
  26.     right_sums = generate_subsets_sums(right_half)
  27.  
  28.     # Проводим попарное сравнение элементов из левого и правого множеств
  29.     for left_sum in left_sums:
  30.         complement = target_sum - left_sum
  31.         if any(abs(complement - right_sum) <= tolerance for right_sum in right_sums):
  32.             return True
  33.     return False
  34.  
  35. print(is_subset_sum_possible(a, s))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement