List all possible numbers from a given array that sums up to a given number

I have to solve the following problem: Given an array of integers and given an integer value, list all possible numbers frm the array that sums up to the given value.

Example:

Input: array = {1, 2, 2, 3, 4, 5}, int N = 5

Output: {1, 2, 2}, {1, 4}, {5} {2, 3}.

This is my solution:

import java.util.ArrayList;
public class SubSum {
    static ArrayList> res;
    public static void main(String[] args) {
        int arr[] = {1, 2, 2, 3, 4, 5};
        int N = 5;
        solve(arr, N);
        for (int i = 0; i  curr = new ArrayList();
        int tmp = 0;
        int currPostion;
        helper(arr, n, tmp, curr, 0);
    }

    private static void helper(int[] arr, int n,
            int tmp, ArrayList curr, int currPosition) {
        while(currPosition  n)){
                    helper(arr, n, tmp, curr, currPosition+1);
                    if(curr.size() >= 1){
                        int lastIndex = curr.size()-1;
                        int lastEl = curr.remove(lastIndex);
                        helper(arr, n, tmp-lastEl, curr, currPosition+1);
                    }
                }
            }
        }
    }
}

I couldn't come up with something faster than exhaustive search. Is this the best possible approach? Also any comments about the code are welcome. I don't like it much, since it looks more like functional programming than object oriented, but I don't know how to improve in this direction.

I think the cleanest solution is to first make one pass through the list, storing the numbers in a data structure. Then use the data structure to perform the calculation.

Data Structure

You want to know how many times you've seen a particular number.

Because the input numbers repeat you can't use a java.util.Set or java.util.BitSet.

The simplest solution is to use a java.util.Map (like java.util.HashMap) where the key is the number and the value is how many times you've seen it.

It doesn't really matter what data structure you use, as long as you can easily look up whether a number has been seen or not. (Finding that information in the original array is slow!)

Example

Input = {1, 4, 4, 3}, N=5

Process input 1

store (1->1) in the map.

Process input 4

store (4->1) in the map.

Process input 4

Kick out the old value (4->1), and replace it with (4->2).

Process input 3

Store (3->1) in the map.

Final result: ((1->1), (3->1), (4->2))

The pattern is: you retrieve the old value and if it's not null you add one to it.

Search for Solutions

The cleanest solution is to write something recursive.

One input is your data structure (see above), which tells you what numbers are available.

The other input is what your total number is.

Initial Conditions

Input = {1, 2, 2, 3, 4, 5}, N=5

Data structure = (1->1, 2->2, 3->1, 4->1, 5->1)

This means that 1,3,4,5 have been seen once, and 2 has been seen twice.

Start the search

Data structure = ((1->1), (2->2), (3->1), (4->1), (5->1)), N=5

Case 1: Find 5's

Five has been seen, so it's a valid solution. Print out 5 and you're done.

Case 2: Find 4's

There is still a four remaining.

Add a four to an internal list.

Make a copy of the data structure. (*)

Decrement the number of 4s from your data structure.

Recursively search for things that add up to 1. (5-4=1).

Case 3: Find 3's

There is still a three remaining.

Add a three to an internal list.

Make a copy of the data structure. (*)

Decrement the number of 3s from your data structure.

Recursively search for things that add up to 2. (5-3=2)

Case 3: Find 2's

(Same pattern as above.)

Case 4: Find 1's

(Same pattern as above.)

Print the results

When you get to the bottom of your recursion, print the current number plus all the previous numbers.

(*) There's a more efficient way of doing this that doesn't involve making a copy: modify the data structure, make the recursive call, then reset the data structure. This technique is easy to get wrong, and it's a good place to cut corners unless you really have the time to polish your code.

Functional vs. Object-Oriented Programming

I don't see anything wrong with using functional programming for this assignment. There's no reason why you need to create multiple classes, and it's only meaningful to talk about object-oriented programming when there is more than one class.

If you want to, you could create multiple classes with clearly defined responsibilities. One could hold the data, one could perform the search, and a third could supply the initial conditions.

StackExchange Code Review Q#56270, answer score: 12