Subset Issue - Greplin Call

Question

I struggled with the 3rd difficulty level of Greplin. For those who are not familiar, here is the problem:

For the final task, you must find all subsets of the array, where the largest number is the sum of the remaining numbers. For example, to enter:

(1, 2, 3, 4, 6)

subsets would be

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

Here is a list of numbers that you must run your code. Password is the number of subsets. In the above case, the answer will be 4.

3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99

I managed to program a solution that will build all 4 million plus combinations of 22 numbers, and then check them all, which will give me the correct answer. The problem is that it takes a break of 40 minutes. An Internet search seems that several people were able to write an algorithm to get an answer in less than a second. Can someone explain in pseudo code a better way to handle this than the computationally expensive brute force method? Its driving me nuts!

Answer 1

The trick is that you only need to keep track of the number of possible ways to do something. Since the numbers are sorted and positive, it's pretty easy. Here is an effective solution. (It takes less than 0.03 seconds on my laptop.)

#! /usr/bin/python numbers = [ 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99] max_number = max(numbers) counts = {0: 1} answer = 0 for number in numbers: if number in counts: answer += counts[number] prev = [(s,c) for (s, c) in counts.iteritems()] for (s, c) in prev: val = s+number; if max_number < val: continue if val not in counts: counts[val] = c else: counts[val] += c print answer 

Answer 2

We know that the values ​​are nonzero and grow monotonously from left to right.

The idea is to list the possible amounts (any order, from left to right in order) and then list the subsets to the left of this value, because the values ​​on the right cannot participate (they would make the amount too large). We do not need to instantiate the set; as we consider each value, see how it affects the amount. It can be too large (just ignoring this value cannot be in the set), right (its last member in the set), or too small, and at what point it can or cannot be set.

[This problem made me play with Python for the first time. Fun.]

Here's the Python code; according to Cprofile.run it takes .00772 seconds on my P8700 2.54Ghz laptop.

 values = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99] def count(): # sort(values) # force strictly increasing order last_value=-1 duplicates=0 totalsets=0 for sum_value in values: # enumerate sum values if last_value==sum_value: duplicates+=1 last_value=sum_value totalsets+=ways_to_sum(sum_value,0) # faster, uses monotonicity of values return totalsets-len(values)+duplicates def ways_to_sum(sum,member_index): value=values[member_index] if sum<value: return 0 if sum>value: return ways_to_sum(sum-value,member_index+1)+ways_to_sum(sum,member_index+1) return 1 

The resulting number I get is 179. (Corresponds to another poster.)

EDIT: ways_to_sum can be partially implemented using a tail recursion loop:

 def ways_to_sum(sum,member_index): c=0 while True: value=values[member_index] if sum<value: return c if sum==value: return c+1 member_index+=1 c+=ways_to_sum(sum-value,member_index) 

This requires: .005804 seconds: -} The same answer.

Answer 3

This takes less than 5 ms to complete (python). It uses a dynamic programming option called memoized recursion. The go function calculated the number of subsets of the first elements p+1 , which are summed up to target . Since the list is sorted enough to call the function once for each element (like target ) and summarize the results:

 startTime = datetime.now() li = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99] memo = {} def go(p, target): if (p, target) not in memo: if p == 0: if target == li[0]: memo[(p,target)] = 1 else: memo[(p,target)] = 0 else: c = 0 if li[p] == target: c = 1 elif li[p] < target: c = go(p-1,target-li[p]) c += go(p-1, target) memo[(p,target)] = c return memo[(p,target)] ans = 0 for p in range(1, len(li)): ans += go(p-1, li[p]) print(ans) print(datetime.now()-startTime) 

Answer 4

It works

 public class A { static int[] a = {3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99}; public static void main(String[] args) { List<Integer> b = new ArrayList<Integer>(); int count = 0; for (int i = 0; i < a.length; i++) { System.out.println(b); for (Integer t:b) { if(a[i]==t) { System.out.println(a[i]); count++; } } int size = b.size(); for (int j = 0; j < size; j++) { if(b.get(j) + a[i] <=99) b.add(b.get(j) + a[i]); } b.add(a[i]); } System.out.println(count); } } 

pseudocode (with explanation):

• save the following variables

  i.) 'count' of the subsets so far

  ii.) an array b containing the sums of all possible subsets

  2. Go back through the array (say a). for each element a [i]

  i.) pass through array b and count the number of occurrences a [i]. add this to 'count'

  ii.) pass through array b and for each element b [j] .add (a [i] + b [j]) to b, because this is the possible sum of the subset. (if the element a [i] + b [j]> max in a, u can ignore to add it)

  iii.) add [i] to b.

3.u have an account :)

Answer 5

I used the combination generator class in Java, available here:

http://www.merriampark.com/comb.htm

Iterating through combos and finding valid subsets took less than a second. (I do not think that using external code is appropriate for the task, but I also did not apply it.)

Answer 6

 public class Solution { public static void main(String arg[]) { int[] array = { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99 }; int N = array.length; System.out.println(N); int count = 0; for (int i = 1; i < 1 << N; i++) { int sum = 0; int max = 0; for (int j = 0; j < N; j++) { if (((i >> j) & 1) == 1) { sum += array[j]; max = array[j]; } } if (sum == 2 * max) count++; } System.out.println(count); } public static boolean isP(int N) { for (int i = 3; i <= (int) Math.sqrt(1.0 * N); i++) { if (N % i == 0) { System.out.println(i); // return false; } } return true; } } 

Hope this helps, but don't just copy and paste.

Answer 7

I don’t want to beat a dead horse, but most of the solutions posted here miss the key opportunity for optimization and therefore take 6 times as long to complete.

Instead of iterating through the input array and searching for the sums corresponding to each value, it is much more efficient to calculate all possible RELEVANT sums only once, and then see which of these sums is displayed in the original input array. (The “corresponding” sum is the sum of the subset <= the maximum value in the array.)

The second approach works about 6 times faster - usually milliseconds, not seconds - simply because it calls the recursive function to determine the sum about 1/6 so many times!

The code for this approach and a full explanation can be found in this github repo (this is in PHP, because the one that called the one who gave me this task):

https://github.com/misterrobinson/greplinsubsets