Given a number and an array find all possible combinations that sum up to given number

Question

I was asked about this program in an interview. The task is given an integer array as input and another number say target, find all possible combinations in array that sum up to given target.

Example:

array = [1,2,1,1,1]
target = 3

expected result : [1,2],[1,1,1],[2,1],[2,1]

I have come up with below code:

public static void main(String args[]) {
    Integer[] numbers = { 1, 2, 1, 1, 1 };
    int target = 3;
    process(numbers, target);
}

private static void process(Integer[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int sum = 0;

        for (int j = i; j < numbers.length; j++) {
            sum += numbers[j];
            if (sum == target) {
                for (int k = i; k <= j; k++) {
                    System.out.print(numbers[k] + " ");
                }
                System.out.println();
            }
        }
    }
}

But this code only prints 3 combinations : [1 2], [2 1], [1 1 1]

What is the correct way to do this? Is there any other better solution.

Your expected result is wrong. It should be: [1,2],[1,1,1],[2,1],[2,1],[1,1,1],[1,1,1],[1,1,1] (not necessarily in that order). This is because any one of the last three 1's could be replaced with the first 1 and still add up to 3. — Jason, Feb 24 '20 at 21:26
Your algorithm considers only contiguous subarrays, but your problem statement seems to be about arbitrary combinations. — M Oehm, Feb 24 '20 at 21:31
I'd mask the array bit-like - in first iteration take the ```numbers[0]```, in second ```numbers[1]```, then ```numbers[0]``` and ```numbers[1]``` and so on - and check every masking if it matches the target. — mcjmzn, Feb 24 '20 at 21:33
Even my expected result above is wrong. The [2,1] pair should appear three times because there are three 1's after the 2: [1,2],[1,1,1],[2,1],[2,1],[2,1],[1,1,1],[1,1,1],[1,1,1] — Jason, Feb 24 '20 at 21:48
Does this answer your question? [Finding the smallest sub-array that adds up to a given sum (Duplicates are allowed)](https://stackoverflow.com/questions/55621088/finding-the-smallest-sub-array-that-adds-up-to-a-given-sum-duplicates-are-allow) — Prune, Feb 24 '20 at 22:37
If you search in your browser for "Java target sum problem", you'll find references that can explain this much better than we can manage here. — Prune, Feb 24 '20 at 22:37

score 2 · Answer 1 · answered Feb 24 '20 at 21:44

This is an excellent candidate for using recursion:

public static void main(String args[]) {
    Integer[] numbers = { 1, 2, 1, 1, 1 };
    int target = 3;

    for(int i = 0; i < numbers.length; i++) {
        recurseAdd(i, numbers, new ArrayList<Integer>(), 0, target);
    }
}

private static void recurseAdd(int currentIndex, Integer[] numbers, List<Integer> usedNumbers, int sum, int target) {
    if (currentIndex >= numbers.length) {
        return;
    }

    sum = sum + numbers[currentIndex];
    usedNumbers.add(numbers[currentIndex]);

    if (sum == target) {
        System.out.println(usedNumbers);
        return;
    }

    if (sum > target) {
        return;
    }

   for (int i = currentIndex + 1; i < numbers.length; i++) {
        recurseAdd(i, numbers, new ArrayList<>(usedNumbers), sum, target);
    }
}

score 1 · Answer 2 · answered Feb 24 '20 at 21:39

You can do something like this using backtracking:

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    Arrays.sort(candidates);
    int start = 0; 

    backtrack(candidates, target, start, result, temp);

    return result;
}

public void backtrack(int[] candidates, int remaining, int start, List<List<Integer>> result, List<Integer> temp) {
    if(remaining == 0) { 
        result.add(new ArrayList<>(temp)); 
        return;
    }

    if(remaining < 0) { return; }

    for(int i = start; i < candidates.length; i++) {
        temp.add(candidates[i]);
        backtrack(candidates, remaining - candidates[i], i, result, temp);
        temp.remove(temp.size() - 1);
    }
}

You can read more about backtracking and similar approaches.

Given a number and an array find all possible combinations that sum up to given number

2 Answers2