subset sum problem

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

http://en.wikipedia.org/wiki/Subset_sum_problem

Given a set of integers find all subsets summing up to zero.

-- mroman

Options

exec is denied

no deadline, the server will not save your submission

Sample input:_

-35 56 -18 50 -17 0 21 -62 -80 75
88 -23 -2 -54 -41 -97 50 -7 93 56
-87 -14 54 22 96 -75 -37 98 -56 -7
-40 -16 100 22 -81 -90 92 -77 95 43
40 -35 94 -35 96 96 -99 -19 74 -52
-14 82 60 -30 -30 12 -3 -57 20 -35
87 -75 42 -7 -54 -55 51 100 -99 5
-56 -70 -38 23 -67 20 100 -59 89 -42
-8 -60 44 -17 41 42 17 43 -54 -23
30 80 -96 96 -84 47 88 -48 -40 -89
56 52 -19 28 88 26 -86 45 82 -56
52 -29 80 -23 -61 58 92 -4 -4 51
-33 46 -93 38 82 -29 -32 90 17 77
-74 -4 65 41 78 -42 -57 1 -49 3
-99 -42 -41 26 0 -65 54 83 12 -36
19 21 -15 -45 -81 -41 -21 -16 57 60
95 -39 -60 -76 -9 40 99 -61 62 -51
93 -42 94 -54 -49 -95 -39 -37 12 -48
-21 49 4 77 78 1 68 -26 22 -46
73 6 -89 99 76 -33 -32 79 -86 4
13 95 15 43 -100 28 -94 76 -11 73
-87 58 -91 46 -66 -87 3 10 -42 29
-64 67 48 -17 -68 -43 67 54 61 90
98 -17 54 -39 52 -64 80 37 28 -60
-58 5 31 96 81 -21 32 37 74 -37
-73 -96 -38 16 36 -57 -71 -100 -74 -80
-6 37 -2 37 -89 -45 -60 -95 -6 -46
8 -68 71 -49 -97 -63 62 54 82 79
-93 -31 94 80 19 74 -9 -83 32 -47
-42 26 -8 81 23 49 5 -5 55 -98

Sample output:

[[0]]
[[-97,-54,-41,-7,50,56,93],[-97,-54,-41,-2,50,56,88],[-97,-54,-23,-7,88,93],[-97,-41,50,88],[-97,-7,-2,50,56],[-54,-2,56],[-41,-7,-2,50]]
[[-87,-56,-37,-14,96,98],[-87,-56,-7,54,96],[-75,-56,-14,-7,54,98],[-75,-14,-7,96]]
[[-90,-81,-16,92,95],[-81,-77,-40,-16,22,92,100],[-77,-40,22,95]]
[[-99,-52,-19,74,96],[-99,-52,-19,74,96],[-99,-35,40,94],[-99,-35,40,94]]
[[-57,-35,12,20,60],[-57,-3,60],[-35,-30,-14,-3,82],[-35,-30,-14,-3,82],[-30,-30,60]]
[[-99,-75,-55,42,87,100],[-75,-54,42,87]]
[[-70,-59,-42,-38,20,89,100],[-70,-42,23,89],[-67,-56,23,100],[-67,-42,20,89]]
[[-60,-54,-23,-8,17,41,43,44],[-60,-23,-17,17,41,42],[-60,-23,41,42],[-60,-17,-8,41,44],[-60,-17,-8,42,43],[-60,17,43],[-54,-23,-17,-8,17,41,44],[-54,-23,-17,-8,17,42,43],[-54,-23,-8,41,44],[-54,-23,-8,42,43],[-17,17]]
[[-96,-48,-40,88,96],[-96,96],[-89,-84,-48,-40,30,47,88,96],[-89,-84,30,47,96],[-48,-40,88]]
[[-86,-56,-19,28,45,88],[-86,-56,26,28,88],[-56,56]]
[[-61,-23,-4,-4,92],[-29,-23,52]]
[[-33,-32,-29,17,77]]
[[-74,-57,-49,-4,41,65,78],[-74,-49,1,3,41,78],[-74,-42,-4,1,41,78],[-74,-4,78],[-57,-49,-4,1,3,41,65],[-57,-49,41,65],[-42,1,41],[-4,1,3]]
[[-42,-41,0,83],[-42,-41,83],[0]]
[[-81,-45,-16,-15,19,21,57,60],[-81,-41,-16,21,57,60],[-81,-21,-15,57,60],[-81,-16,19,21,57],[-81,21,60],[-45,-41,-21,-16,-15,21,57,60],[-45,-41,-16,-15,57,60],[-45,-21,-16,-15,19,21,57],[-45,-21,-15,21,60],[-45,-16,-15,19,57],[-45,-15,60],[-41,-21,-16,21,57],[-41,-16,57],[-21,21]]
[[-76,-61,-60,-51,-39,-9,40,62,95,99],[-76,-61,-60,40,62,95],[-76,-61,-51,-9,40,62,95],[-60,-39,99],[-51,-39,-9,99]]
[[-54,-39,93]]
[[-46,-26,1,22,49],[-46,-26,4,68],[-26,4,22]]
[[-89,-86,76,99],[-89,4,6,79],[-86,4,6,76]]
[[-100,-94,-11,13,15,28,73,76],[-100,-94,-11,13,43,73,76],[-100,-94,13,15,28,43,95]]
[[-91,-42,29,46,58],[-87,29,58],[-87,29,58],[-42,3,10,29]]
[[-68,-64,-43,-17,48,54,90],[-68,-43,-17,61,67],[-68,-43,-17,61,67]]
[[-64,-60,-39,-17,28,54,98],[-64,-60,-39,28,37,98]]
[[-58,-37,-21,5,37,74],[-58,-21,5,74],[-37,5,32],[-37,37]]
[]
[[-60,-6,-6,-2,37,37]]
[[-97,-68,-63,-49,8,54,62,71,82],[-97,-68,-63,-49,54,62,79,82]]
[[-93,19,74]]
[[-98,-42,-8,-5,23,26,49,55],[-98,-42,-8,-5,23,49,81],[-98,-5,5,23,26,49],[-98,23,26,49],[-42,-8,-5,55],[-5,5]]

Sample input:_

73 67 61 72 -71 69 36 -86 18 -67
-60 -54 41 27 -14 -89 84 41 -94 79
-95 -5 -33 9 74 -3 52 -72 -63 -17
-50 -80 48 47 -32 34 22 33 -95 -62
-77 22 -56 -59 -89 0 -74 51 34 18
-97 67 -64 -90 -65 -50 -47 -74 -60 54
-40 -20 55 -10 -59 73 -90 -95 -94 42
97 -34 31 69 -34 72 26 32 -83 -50
39 68 -29 -54 62 -92 -80 -12 -54 -44
-24 -56 1 5 17 45 -79 -20 -93 48
-20 73 -76 -31 -67 86 96 96 -85 11
-22 28 11 -71 -35 61 52 17 66 -3
76 -94 -35 18 -24 82 -20 73 72 27
-46 -64 -47 56 -94 -12 72 -85 23 -90
55 -24 -58 -66 -22 -11 1 40 94 63
-94 -42 -51 -34 -39 -43 -77 54 -94 -9
37 35 96 13 73 30 37 10 -98 -71
52 -80 -65 -21 44 -17 -28 -32 17 33
77 77 -97 -88 79 77 -2 43 75 29
-5 73 -33 36 38 -80 -73 98 5 58
-1 -84 -52 45 -42 24 -66 84 -32 -12
-61 -33 14 -59 -73 -99 99 49 -52 -66
-52 -29 -87 -68 -87 -24 -68 -48 -60 -34
36 -96 -34 83 93 -9 97 -59 -79 -26
85 -80 48 69 13 1 -19 -59 28 42
91 56 -92 85 67 -86 61 48 58 -93
-40 46 -36 53 51 46 -39 19 -83 54
89 86 93 -75 7 -70 91 -34 50 -1
-66 -94 22 50 -28 33 53 -90 -75 -73
-16 26 -50 -52 76 51 -14 -61 -46 84

Sample output:

[[-86,-71,-67,18,61,72,73],[-86,-71,18,67,72],[-67,67]]
[[-89,-60,-14,79,84],[-54,-14,27,41],[-54,-14,27,41]]
[[-72,-63,9,52,74],[-63,-17,-3,9,74]]
[[-95,47,48],[-80,-50,-32,33,34,47,48],[-80,33,47],[-50,-32,34,48]]
[[-74,0,18,22,34],[-74,18,22,34],[-56,0,22,34],[-56,22,34],[0]]
[[-74,-47,54,67]]
[[-95,-20,42,73]]
[[-83,-50,-34,-34,32,72,97],[-83,-50,-34,26,69,72],[-83,-50,-34,26,69,72]]
[]
[[-93,45,48],[-79,-20,1,5,45,48]]
[[-85,-76,-31,96,96],[-85,-67,-31,-20,11,96,96],[-76,-31,11,96],[-76,-31,11,96],[-76,-20,96],[-76,-20,96]]
[[-71,-35,17,28,61]]
[[-94,-35,-24,-20,18,73,82],[-94,-35,-20,73,76],[-94,-24,18,27,73],[-94,18,76]]
[]
[[-66,-58,-24,-11,1,40,55,63],[-66,-58,-22,-11,63,94],[-66,-58,-11,1,40,94],[-58,-24,-22,1,40,63]]
[]
[[-98,-71,73,96]]
[[-80,-32,-17,33,44,52],[-80,-28,-21,-17,17,33,44,52],[-80,-28,-21,33,44,52],[-65,-32,-28,-21,17,33,44,52],[-32,-28,-17,33,44],[-17,17]]
[[-97,-88,29,77,79],[-97,-88,29,77,79],[-97,-88,29,77,79]]
[[-73,-33,-5,38,73],[-73,-5,5,73],[-73,73],[-33,-5,38],[-5,5]]
[[-84,-32,-12,-1,45,84],[-84,84],[-66,-42,-32,-12,-1,24,45,84],[-66,-42,24,84],[-52,-32,84],[-32,-12,-1,45]]
[[-99,99],[-66,-33,99],[-61,-52,14,99]]
[]
[[-96,-59,-26,-9,93,97],[-59,-34,-26,36,83],[-59,-34,93]]
[[-80,-59,-19,13,28,48,69],[-80,-59,28,42,69],[-80,-19,1,13,85]]
[[-93,-92,-86,58,61,67,85]]
[[-83,-40,-39,19,46,46,51],[-83,-40,19,51,53],[-83,-39,-36,51,53,54],[-83,-36,19,46,54],[-83,-36,19,46,54]]
[[-75,-70,-34,-1,89,91],[-75,-70,-34,86,93],[-75,-70,-1,7,50,89]]
[[-75,-28,50,53],[-75,22,53]]
[[-61,-52,-14,51,76],[-61,-50,-16,51,76],[-61,-16,26,51],[-52,-50,26,76],[-50,-46,-14,26,84],[-46,-16,-14,76]]

Ranking

Python _

Python3 _

Lua _

J _

K _

C _

Haskell _

xgawk _

gs2 _

Nibbles _

Burlesque _

Language Ranking_

return to the top page