CODEWITHSUNDEEP
javaarraysalgorithmsearch
user3150947
user3150947

Reputation: 373

Sum exists in array items

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!

Upvotes: 0

Views: 1404

Answers (1)

fluminis
fluminis

Reputation: 4059

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

Upvotes: 2

Related Questions