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

Question

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<ArrayList<Integer>> 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 < res.size(); i++) {
            for (int j = 0; j < res.get(i).size(); j++) {
                System.out.print(res.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    private static void solve(int[] arr, int n) {
        ArrayList<Integer> curr = new ArrayList<Integer>();
        int tmp = 0;
        int currPostion;
        helper(arr, n, tmp, curr, 0);
    }

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

            }
            else{
                if((arr[currPosition] <= n) && (arr[currPosition] + tmp <= n)){
                    curr.add(arr[currPosition]);
                    helper(arr, n, tmp+arr[currPosition], curr, currPosition+1);
                }
                if((arr[currPosition] <= n) && (arr[currPosition] + tmp > 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.

Answer 1

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.

Answer 2

• It's a bit odd that you mix arrays and ArrayList's.

• Stick to List (the interface) in the variable declarations instead of ArrayList (the implementation).

• You might get a stack overflow with all your recursive calls.

As Jerry Coffin commented, this is really a problem for dynamic programming: Instead of finding the solution for N, you start at 1 and then from that solution, you solve for 2, etc. until you reach N. When solving for i, you use the solutions you got for 1, ..., (i - 1).

Answer 3

You have received excellent answers already about more efficient approaches, so I'm going to mention a few things which crossed my mind from reading your question and code.

First of all, you say:

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.

To me, this does not look functional at all. All your methods return void. You're storing mutable state in your res variable. This is not functional, this is procedural.

---

Now, about your code. Read this line for me:

helper(arr, n, tmp, curr, 0);

And then answer my questions: Do what with the arr-what, the n-what, tmp-what and curr-what?

Your naming could be improved a lot here. helper can be a helper for anything. Santa's helper? arr would be better named as allAvailableNumbers or simply allNumbers.

tmp is temporary for what exactly?

Making code that documents itself is done primarily by naming methods and variables. Naming things 100% correct are hard, but I believe you can do much better than this. Think more about what your variables are used for than what they are (arr is an array, yeah... but what is the meaning of it?). There's a thing called Hungarian notation where you prefix the name arr (or simply a) to all your array variables. When you've named it arr it's even worse than Hungarian notation as it only contains the prefix. It's Scottish notation. (There's a stereotype that Scottish are cheap, no offense to the Scots.)

---

On another note, you got two useless variables here:

int tmp = 0;
int currPostion;
helper(arr, n, tmp, curr, 0);

just make that:

helper(arr, n, 0, curr, 0);

(But please rename the helper method!)