Question

How to find all possible combinations of numbers from an array that equal to N in Java

Answer 1

import java.util.ArrayList;
import java.util.Arrays;

public class MyClass {
    static void GetCombinationsEqualToN(ArrayList<Integer> arr, int N, ArrayList<Integer> combination) {
       int sum = 0;
       
       for (int num: combination) sum += num;
       
       if (sum == N)
            System.out.println("sum(" + Arrays.toString(combination.toArray()) + ") = " + N);
       
       if (sum >= N)
            return;
            
       for (int i = 0; i < arr.size(); i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             
             for (int j = i + 1; j < arr.size(); j++) remaining.add(arr.get(j));
             
             ArrayList<Integer> combination_next = new ArrayList<Integer>(combination);
             combination_next.add(arr.get(i));
             
             GetCombinationsEqualToN(remaining, N, combination_next);
       }
    }

    public static void main(String args[]) {
        Integer[] arr = {4, 6, 8, 2, 1, 10, 3, 5, 13};
        int N = 13;

        GetCombinationsEqualToN(new ArrayList<Integer>(Arrays.asList(arr)), N, new ArrayList<Integer>());
    }
}




/*
run:

sum([4, 6, 2, 1]) = 13
sum([4, 6, 3]) = 13
sum([4, 8, 1]) = 13
sum([4, 1, 3, 5]) = 13
sum([6, 2, 5]) = 13
sum([8, 2, 3]) = 13
sum([8, 5]) = 13
sum([2, 1, 10]) = 13
sum([10, 3]) = 13
sum([13]) = 13

*/

 

70+ SQL courses for beginners and professionals