fork download
copy 
  1. from itertools import combinations
  2.  
  3. def simple_zero_sum_subset(arr):
  4.     values = set(arr)
  5.     return 0 in values or any(i for i in values if -i in values)
  6.  
  7. def brute_force_zero_sum_subset(arr):
  8.     return any(sum(combo) == 0 for r in xrange(1, len(arr)+1) for combo in combinations(arr, r))
  9.  
  10. # --- TESTING --- #
  11.  
  12. simple_tests = {
  13.     False: [
  14.         [1, 2, 3],
  15.         [-5, -3, -1, 2, 4, 6],
  16.         [],
  17.     ],
  18.     True: [
  19.         [-1, 1],
  20.         [-97364, -71561, -69336, 19675, 71561, 97863],
  21.         [-53974, -39140, -36561, -23935, -15680, 0],
  22.     ]
  23. }
  24.  
  25. assert all(simple_zero_sum_subset(arr) == expected
  26.            for expected, arrs in simple_tests.items()
  27.            for arr in arrs)
  28. print 'Simple tests passed.'
  29.  
  30. bonus_tests = {
  31.     False: [
  32.         [-83314, -82838, -80120, -63468, -62478, -59378, -56958, -50061, -34791, -32264, -21928, -14988, 23767, 24417, 26403, 26511, 36399, 78055],
  33.         [-92953, -91613, -89733, -50673, -16067, -9172, 8852, 30883, 46690, 46968, 56772, 58703, 59150, 78476, 84413, 90106, 94777, 95148],
  34.         [-94624, -86776, -85833, -80822, -71902, -54562, -38638, -26483, -20207, -1290, 12414, 12627, 19509, 30894, 32505, 46825, 50321, 69294],
  35.         [-83964, -81834, -78386, -70497, -69357, -61867, -49127, -47916, -38361, -35772, -29803, -15343, 6918, 19662, 44614, 66049, 93789, 95405],
  36.         [-68808, -58968, -45958, -36013, -32810, -28726, -13488, 3986, 26342, 29245, 30686, 47966, 58352, 68610, 74533, 77939, 80520, 87195],
  37.     ],
  38.     True: [
  39.         [-97162, -95761, -94672, -87254, -57207, -22163, -20207, -1753, 11646, 13652, 14572, 30580, 52502, 64282, 74896, 83730, 89889, 92200],
  40.         [-93976, -93807, -64604, -59939, -44394, -36454, -34635, -16483, 267, 3245, 8031, 10622, 44815, 46829, 61689, 65756, 69220, 70121],
  41.         [-92474, -61685, -55348, -42019, -35902, -7815, -5579, 4490, 14778, 19399, 34202, 46624, 55800, 57719, 60260, 71511, 75665, 82754],
  42.         [-85029, -84549, -82646, -80493, -73373, -57478, -56711, -42456, -38923, -29277, -3685, -3164, 26863, 29890, 37187, 46607, 69300, 84808],
  43.         [-87565, -71009, -49312, -47554, -27197, 905, 2839, 8657, 14622, 32217, 35567, 38470, 46885, 59236, 64704, 82944, 86902, 90487],
  44.     ],
  45. }
  46.  
  47. assert all(brute_force_zero_sum_subset(arr) == expected
  48.            for expected, arrs in bonus_tests.items()
  49.            for arr in arrs)
  50. print 'Bonus tests passed.'
Success #stdin #stdout 0.01s 23352KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Simple tests passed.
Bonus tests passed.
https://ideone.com/Bi4w4X
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!