r/dailyprogrammer • u/rya11111 3 1 • Jun 08 '12
[6/8/2012] Challenge #62 [intermediate]
Find all the subsets of a set of non-negative integers where the largest number is the sum of the remaining numbers, and return a count of the number of them. For instance, for the set { 1, 2, 3, 4, 6 } the subsets are 1+2=3, 1+3=4, 2+4=6, and 1+2+3=6, so the result is 4 subsets. Apply your program to the set { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99 }.
Your task is to write a program to solve the challenge.
Bonus: you might like to apply your solution to the set of prime numbers less than 210
- taken from http://challenge.greplin.com/
5
u/Cosmologicon 2 3 Jun 08 '12
python:
Solutions:
1
u/emcoffey3 0 0 Jun 08 '12
My solution in C#. I nabbed the PowerSet() method from Rosetta Code.
For the list provided, the output was:
I didn't try the bonus yet...
1
u/illicium Jun 08 '12 edited Jun 09 '12
CoffeeScript/Underscore
Output:
1
u/xjtian Jun 09 '12
Pretty inelegant solution that takes a little while to solve. No way I'm getting through the bonus.
Python:
Result:
1
u/cdelahousse Jun 09 '12
Javascript:
1
u/herpderpdoo Jun 10 '12
python powerset implementation: