Spance Spance - 3 months ago 9
Java Question

Java finding all combos in array that add up to specific number

I'm currently working on the following question from a interviewing book:


You are given a random array of 50 unique integers ranging from 1 to 100 inclusive. Write a method using Java that takes in a positive integer as a parameter and returns an array of all the number combinations that add up to that value.


For example, given an array of integers [3,6,1,9,2,5,12] and being passed the integer value 9, you would return [[3,6],[6,1,2],[9],[3,1,5]]. Order of returning the results in the array does not matter, though you should return unique sets (ie. [6,3] and [3,6] are the same and only one should be returned). Also, the individual results should be in the order they are found (ie [6,1,2] should be returned, not [1,2,6]).

I've made decent progress on it, but I fear I may solving this the wrong way.

import java.util.*;


public class findCombinations {
public static void main(String[] args) {
int number;
int[] list = new int[10];
Scanner reader = new Scanner(System.in);

//fill the array
for (int i = 0; i < list.length; i++) {
number = (int)(Math.random() * 10) + 1;
list[i] = number;
for (int j = 0; j < i; j++) { //remove duplicates
if (list[i] == list[j]) {
i--;
break;
}
}
}

Arrays.sort(list);

//test output
for (int i = 0; i < list.length; i++) {
System.out.println(list[i]);
}
System.out.println("Enter a number: ");
int input = reader.nextInt();
ArrayList<Integer> trimmedList = new ArrayList<Integer>();

//cut out the numbers that are impossible to use
for (int i = 0; i < list.length; i++) {
if (list[i] <= input) {
trimmedList.add(list[i]);
}
}
//test output
printList(trimmedList);

ArrayList<Integer> comboList = new ArrayList<Integer>();
System.out.println("Finding combinations...");

for (int i = 0; i < trimmedList.size(); i++) {
int current = trimmedList.get(i);
if (current == input) { System.out.println(current); }
else if (current < input) {
comboList.add(current);
if (isCombo(comboList, input)) {
printList(comboList);
}
else { continue; }
}
else { continue; }
}
}

public static boolean isCombo(ArrayList<Integer> list, int input) {
ArrayList<Integer> combo = new ArrayList<Integer>();
int sum = 0;

for (int i : list)
sum += i;

if (sum == input) { return true; }
else { return false; }
}

public static void printList(ArrayList<Integer> list) {
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
}
}


I know this is incomplete but I wanted to ask if anyone had any suggestions or improvements I could make on this? I sorted my list and trimmed out all the integers that won't possibly be used, but now the hard part is finding all the combos.

Answer

There are many different approaches to solve this problem, each with their own merits, so I wouldn't worry too much about whether your answer is the 'right' one or not...so long as it actually solves the problem! Also, an interviewer will likely be more interested in your thought-process, and the strategies you use, rather than a 100% perfect solution written in the span of a few minutes on a whiteboard.

Here's a couple of things to consider:

  • As you noticed, you can immediately eliminate any integers larger than your target value.

  • You're essentially generating arbitrarily-sized subsets of your starting array—so Set is likely the most useful data type to work with. {2, 3} and {3, 2} should be seen as identical when you're generating your response set.

  • Integer partitioning is an NP-Complete problem. It's hard. I think you've taken the correct approach of starting with the array, rather than with the target value.

  • There are many algorithms for generating combinations of integers from a larger set. Check out this SO answer for a few of them. You can generate k sized combinations from your (already-filtered) starting set, for k from 1-50.

  • Actually...there are more direct ways to get the power set of your starting set. Consider the inherent structure of a power set (shown below). By enumerating a few examples, you'll notice a natural recurrence in your strategy for identifying the subsets.

As you're generating these combinations, discard any whose elements don't sum to your target value.

https://en.wikipedia.org/wiki/Power_set

Image Source: https://en.wikipedia.org/wiki/Power_set