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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Bin_packing_problem). — tobias_k, Apr 21 '16 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, Apr 21 '16 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, Apr 21 '16 at 14:00
Tobias_K, you are welcome to add your answer to receive a V, as you were the first to answer. — user3150947, Apr 21 '16 at 14:04
possible duplicate of http://stackoverflow.com/questions/18305843/find-all-subsets-that-sum-to-a-particular-value — JavaHopper, Apr 21 '16 at 14:29

score 2 · Accepted Answer · answered Apr 21 '16 at 14:07

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

Sum exists in array items

1 Answers1