Sum exists in array items

Question

Suggest I have the following array :

{2,3,4,5,11,6} and I'd like to know if any items of the array contain a sum of the number x.

For example: x=10, then the output would be {2,3,5} and {4,6}. x=13, then the output would be {2,11},{3,4,6} and {2,5,6}

What would be an optimal algorithm to solve this problem?

I have thought of solving this using the possible permutations of the array, and check whether the sum of the beginning of each permutation equals to the X, but it doesn't seem to solve it.

Thanks!

Subset sum problem? Simpler, in fact, as you seem to have only positive numbers. Could also be seen as a special case of bin packing problem. — tobias_k
– tobias_k, Commented Apr 21, 2016 at 13:48
"it doesn't seem to solve it" what makes you think so? creating all possible permutations, adding the sum of those and giving the right ones back might not be efficient, but it will work! — ParkerHalo
– ParkerHalo, Commented Apr 21, 2016 at 13:51
Well, remember, a set of n members has n! possible permutations, which grows very fast. Even if you have only 20 elements in your array, you have 20! permutations, which is something like 2.4*10^18. You will never finish calculating all permutations for relatively small numbers. Better use an algorithm as suggested by tobias_k. — Tobias Brösamle
– Tobias Brösamle, Commented Apr 21, 2016 at 14:00
Tobias_K, you are welcome to add your answer to receive a V, as you were the first to answer. — user3150947
– user3150947, Commented Apr 21, 2016 at 14:04

fluminis · Accepted Answer · 2016-04-21 14:07:34Z

My two cents solution

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class Test { public static void main(String[] args) { List<Integer> list = Arrays.asList(2, 3, 4, 5, 11, 6); Collections.sort(list); Integer sum = 0; Integer max = 13; for (int i=0; i<list.size(); i++) { sumNext(list, i, sum,max, new ArrayList<Integer>()); } } private static void sumNext(List<Integer> list, int pos, Integer currentSum, Integer max, List<Integer> currentElement) { int nextSum = currentSum + list.get(pos); if (nextSum > max) { return; } currentElement.add(list.get(pos)); if (nextSum == max) { for (Integer i : currentElement) { System.out.print(i); System.out.print(" "); } System.out.println(); } else if (nextSum < max && list.get(pos) < max - currentSum) { // as array is sorted if current element is higher than the diff // between currentSum and max there is no need to try with next // element for (int i=pos+1; i<list.size(); i++) { sumNext(list, i, nextSum, max, currentElement); } } currentElement.remove(list.get(pos)); } }

Will output:

max=10
2 3 5
4 6
max=13
2 5 6
2 11
3 4 6

Collectives™ on Stack Overflow

Sum exists in array items

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related