mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
96 lines
2.5 KiB
Python
96 lines
2.5 KiB
Python
def check(t):
|
|
print()
|
|
sum = 0
|
|
for x in t:
|
|
sum += x
|
|
|
|
# odd sum cannot be divided by two
|
|
if sum % 2 != 0:
|
|
print(t, sum)
|
|
print("sum odd")
|
|
return False
|
|
|
|
# for ease
|
|
t.sort()
|
|
print(t, sum)
|
|
|
|
# count the half, or the closest thing to it
|
|
half = 0
|
|
close_to_half_list = []
|
|
i = len(t) - 1
|
|
while half < sum // 2:
|
|
half += t[i]
|
|
close_to_half_list.append(t[i])
|
|
i -= 1
|
|
|
|
# half is already half of the sum == is possible to
|
|
# halve the sum_list
|
|
if half == sum // 2:
|
|
print(half, "==", sum // 2)
|
|
return True
|
|
|
|
# remove the overgoing sum value
|
|
half -= close_to_half_list.pop()
|
|
print(close_to_half_list)
|
|
|
|
# number we need to be == half
|
|
needed_sum = sum // 2 - half
|
|
print(needed_sum)
|
|
|
|
# if needed sum is already somewhere in the
|
|
# sum_list and is not already used for making the half
|
|
if needed_sum in t and needed_sum not in close_to_half_list:
|
|
return True
|
|
|
|
# for i, x in enumerate(t):
|
|
# if x > needed_sum:
|
|
# continue
|
|
# if x in close_to_half_list:
|
|
# continue
|
|
# for j, y in enumerate(t):
|
|
# # print(x, "+", y, "=", x + y, "==", needed_sum)
|
|
# if y + x == needed_sum:
|
|
# # print(" ****** THIS ******* ")
|
|
# if y not in close_to_half_list and i != j:
|
|
# return True
|
|
|
|
global result, sum_list
|
|
result = set()
|
|
sum_list = set()
|
|
find_sum_rec(0, len(t), t)
|
|
print("result", result)
|
|
|
|
# for x in result:
|
|
# print(x)
|
|
|
|
return False
|
|
|
|
|
|
def find_sum_rec(k, n, t):
|
|
global sum_list
|
|
print(k, n)
|
|
|
|
if k == n:
|
|
print("dict", sum_list)
|
|
# result.add(frozenset(sum_list))
|
|
# sum_list = set()
|
|
else:
|
|
for x in range(0, 2):
|
|
print("k,x", k, x)
|
|
if x != 0:
|
|
sum_list.add(t[k])
|
|
print("sum_list", sum_list)
|
|
find_sum_rec(k + 1, n, t)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
# print(check([3, 4, 5])) # False doenst work
|
|
# print(check([16, 8, 4, 4])) # True
|
|
# print(check([9, 4, 8, 7, 6])) # True
|
|
# print(check([1, 2, 3, 4, 5, 6])) # False
|
|
# print(check([1, 2, 3, 4, 5, 6, 7])) # True doesnt work
|
|
# print(check([4, 4, 4, 6, 6])) # True
|
|
# print(check([10, 27, 15, 6, 17, 22, 1, 22])) # True
|
|
# print(check([10, 4, 9, 1])) # False
|
|
print(check([30, 8, 28, 11, 4, 16, 10, 3])) # True
|