Find all combinations of numbers of a set that add up to a given target - avoid for loops

I am thinking about the following problem:

Consider a 3-numbers lock, i.e. a lock which has three little number wheels that opens whenever the sum of these three numbers equals 75. I know, this doesn't make sense for a lock, but just imagine this. The number wheels have numbers 3, 15, 17, 35, 40, 25, 5, 13. I am allowed to use numbers multiple times, i.e. in order to reach 75, I could use the combination 25, 25, 25.

I want to come up with all possible combinations to solve this puzzle. I have a solution and it works fine for just 3 different number wheels. But since I am using 3 for-loops for this, I know I cannot extend this code to work for, say a 100 number-wheels lock. I don't even know if this was possible (maybe recursively, but I always have troubles understanding recursion). Anyways, I really want to make this code look a little nicer. It is okay for me to leave the number of iterations the same, but I really want to get rid of the 3 for-loops, because I kind of want to extend this code to be a 10-numbers lock and in that case I would have 10 for-loops which looks ridiculous. There should be a way to leave out the for loops, I think

So, enough said. Here is my solution:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestClass {

public static void main(String[] args) {

List<List<Integer>> solutions = new ArrayList<>();
List<Integer> combinations = new ArrayList<Integer>();

List<Integer> numbers = new ArrayList<Integer>();

int target = 75;

int var1 = 3;
int var2 = 3;
int var3 = 3;

for (int i = 0; i < numbers.size(); i++) {
var1 = numbers.get(i);
for (int j = 0; j < numbers.size(); j++) {
var2 = numbers.get(j);
for (int k = 0; k < numbers.size(); k++) {
var3 = numbers.get(k);

int sum = var1 + var2 + var3;
if (sum == target) {

Collections.sort(combinations);
if (!solutions.contains(combinations)) {
}
combinations = new ArrayList<>();
}
}
}
}

for (List<Integer> solution: solutions) {
System.out.println(solution);
}

}
}


Any ideas, please share them with me :-)

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. May 7 '21 at 12:06
• oh, ok. I didn't know that.
– Luk
May 7 '21 at 12:59

you need the function

public static List<Integer> get_next_highest(List<Integer> combinations, List<Integer> numbers) {
for(int i=0; i < combinations.size(); i++) {
if(combinations[i]<numbers.size()-1) {
combinations[i]++;
return combinations;
}
else combinations[i] = 0;
}
return null;
}


here, to simplify I've made combinations have indices (otherwise can't just do combinations[i]++, would need to find the next highest number in numbers)...

for eg. if numbers=[25 30 60 80] and combinations=[0 0 2 1]

this corresponds to the wheel positions [25 25 60 30]

if you pass the value of combinations [3 3 3 3] the function will return a null so make sure to do a check and stop when it does.

This will loop you through all possible combinations if you start at [0 0 0 0]

Specifically in the order [0 0 0 0] [1 0 0 0 ] [2 0 0 0] [3 0 0 0] [0 1 0 0] [1 1 0 0] ... [3 3 3 3]

should be fairly easy to sum up numbers[combinations[i]]

since you specified no for loops here's the recursive version

public static List<Integer> get_next_highest(List<Integer> combinations, List<Integer> numbers, int i=1) {
if(i==combinations.size()) return null;
if(combinations[i]<numbers.size()) {
combinations[i]++;
return combinations;
}
else {
combinations[i] = 0;
return get_next_highest(combinations, numbers, i+1);
}
}


it does the same thing

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestClass {

public static void main(String[] args) {

List<List<Integer>> solutions = new ArrayList<>();
List<Integer> combinations = new ArrayList<Integer>();

List<Integer> numbers = new ArrayList<Integer>();

int target = 75;
int num_wheels = 3;

for (int i = 0; i < num_wheels; i++) combinations.add(0);

for (; combinations != null; combinations=get_next_highest(combinations, numbers)) {
int sum = 0;
for(Integer x : combinations) sum += numbers[x];
if (sum == target) {
temp = new ArrayList<>();
Collections.sort(temp);
}
}

for (List<Integer> solution: solutions) {
System.out.println(solution);
}

}
}

• Hi, thx a lot for your answer! Unfortunately, I don't really understand how to apply this function to my problem. Could you try and integrate it into my example? ... also: I am thinking there might be a neat solution that makes use of streams. I have updated my question a little bit with these thoughts
– Luk
May 7 '21 at 10:15
• you can replace your triple loop with this function, loop until the get_next_highest returns a null, otherwise it doesn't deviate from the original post much May 7 '21 at 13:34
• oh, and you also have to do sum of numbers[combinations[i]] instead of sum of combinations[i] May 7 '21 at 13:36