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.