Skip to main content
Code Review

Return to Question

Question Protected by Jamal
Tweeted twitter.com/#!/StackCodeReview/status/485836358322491392
added 190 characters in body; edited title
Source Link
Jamal
Jamal
  • 35.2k
  • 13
  • 134
  • 238

List all possible numbers from a given array that sums up to a given number (Java solution)

Example: Input

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

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 wellcomewelcome. I dontdon'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.

List all possible numbers from a given array that sums up to a given number (Java solution)

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

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 wellcome. I dont like it much, since it looks more like functional programming than object oriented, but I don't know how to improve in this direction.

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

Example:

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

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.

Source Link
user3371223
user3371223
  • 861
  • 4
  • 12
  • 22

List all possible numbers from a given array that sums up to a given number (Java solution)

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 wellcome. I dont like it much, since it looks more like functional programming than object oriented, but I don't know how to improve in this direction.