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

Question

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>();
        numbers.add(3);
        numbers.add(15);
        numbers.add(17);
        numbers.add(35);
        numbers.add(40);
        numbers.add(25);
        numbers.add(5);
        numbers.add(13);
        
        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) {
                        combinations.add(var1);
                        combinations.add(var2);
                        combinations.add(var3);

                        Collections.sort(combinations);
                        if (!solutions.contains(combinations)) {
                            solutions.add(combinations);
                        }
                        combinations = new ArrayList<>();
                    }
                }
            }
        }
    
        for (List<Integer> solution: solutions) {
            System.out.println(solution);
        }
        
    }
}

Any ideas, please share them with me :-)

Answer 1

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>();
        numbers.add(3);
        numbers.add(15);
        numbers.add(17);
        numbers.add(35);
        numbers.add(40);
        numbers.add(25);
        numbers.add(5);
        numbers.add(13);
        
        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<>();
                 for(Integer x : combinations) temp.add(numbers[x]);
                 Collections.sort(temp);
                 if (!solutions.contains(temp)) solutions.add(temp);
             }
        }
    
        for (List<Integer> solution: solutions) {
            System.out.println(solution);
        }
        
    }
}