Como obtener todas las combinaciones sin repetición de un array de números en java?

Question

Tengo un arreglo de longitud n que quiero obtener recursivamente todas las combinaciones sin repetición que den como resultado un número x... por ejemplo, para que el arreglo [1, 3, 5] sume 6 tiene las siguientes combinaciones [1, 5] [5, 1]

El problema es que mi código me genera como combinación [3, 3], repitiendo 3 más de una vez... Este es mi código:

 public static void main(String[] args) {
        int numero = 4;
        ArrayList<Integer> list = new ArrayList();
        Integer[] array = {1, 3, 5};
        combinaciones(array, 0, 0, 6, list);
     
        
        String s = (Recorrer(array, 6, 0, 0)) ? "Si" : "No";
            System.out.println(s);
    }

    private static void combinaciones(Integer[] array, int contador, int index, int objetivo, ArrayList<Integer> list) {
        if (contador == objetivo) {
            System.out.println(list);
        } else {
            for (int i = 0; i < array.length; i++) {
                contador += array[i];
                List<Integer> lista= Arrays.asList(array);
                if (contador <= objetivo && list.size()<array.length) {
                    list.add(array[i]);
                    combinaciones(array, contador, index, objetivo, list);
                    list.remove(list.indexOf(array[i]));
                }
                contador -= array[i];
            }
        }
    }

Answer 1

Manejando un poco de matemáticas podemos simplificar la propuesta de algoritmo; si nosotros vemos, tenemos un número al cual podemos buscar su complemento.

a + b = c
a = c - b

Entonces sabiendo eso, podemos buscar el índice del número que corresponda al complemento.

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        Integer[] array = {1, 3, 5};
        getCombinations(array, 0, 6);
    }

    public static void getCombinations(Integer[] nums, int idx, int search){

        int complement = Arrays.asList(nums).indexOf(search - nums[idx]);
        if (complement > -1 && idx != complement) {
            System.out.println(nums[idx] + " + " + nums[complement]);
        }

        if (++idx < nums.length) {
            getCombinations(nums, idx, search);
        }
    }

}

Como vemos, el algoritmo se simplifica.

Anotaciones

• Se busca el complemento en esta línea Arrays.asList(nums).indexOf(search - nums[idx]);
• Se compara si el complemento es igual al índice del número que se tiene, en ese caso se ignora y se pasa a la siguiente llamada. Esto se aprecia con la condición idx != complement. Esto dará la posibilidad de números iguales, pero de diferente índice. Por ejemplo Integer[] array = {1, 3, 3, 5}; da la posibilidad de [3, 3]
• Si se quiere ignorar los números, basta con decir que son diferentes los valores de los índices o creando un Set

Edit 3 : Solución final

Añadiendo para n combinaciones llegué a la siguiente solución recursiva:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.stream.Collectors;

public class Main {

    static HashSet<ArrayList<Integer>> result = new HashSet<>();

    public static void main(String[] args) {
        Integer[] array = {1, 3, 5, 2 , -1, 9};
        ArrayList<Integer> nums = new ArrayList<>(Arrays.asList(array));
        int search = 8;

        if(
                nums.stream().noneMatch(num -> num < 0)
                && nums.stream().reduce(0, Integer::sum) < search
        ){
            System.out.println("No hay combinaciones");

        } else if(
                nums.stream().noneMatch(num -> num > 0)
                && nums.stream().reduce(0, Integer::sum) > search
        ){
            System.out.println("No hay combinaciones");

        } else {
            getNCombinations(nums, 0, search, search);
            System.out.println(result);
        }
    }

    public static ArrayList<Integer> getNCombinations(ArrayList<Integer> nums, int idx, int search, int abs) {

        ArrayList<Integer> combinations = new ArrayList<>(2);

        int temp2 = nums.remove(idx);
        for (int i = 0; i < nums.size(); ++i) {
            combinations = getNCombinations(nums, i, search - temp2, abs);
            combinations.add(nums.get(i));
            combinations.add(temp2);
            if (combinations.stream().distinct().reduce(0, Integer::sum) == abs)
                result.add(combinations.stream().distinct().collect(Collectors.toCollection( ArrayList::new ) ));
        }
        nums.add(idx, temp2);

        if (++idx < nums.size()) {
            getNCombinations(nums, idx, search, abs);
        }

        return combinations;
    }
}

Anotaciones

• Se hace uso de un HashSet para evitar soluciones duplicadas
• Al HashSet se le añaden ArrayLists filtrando los elementos iguales (simulando un Set) result.add(combinations.stream().distinct().collect(Collectors.toCollection( ArrayList::new ) ));
• Dado a que se mencionan que se pueden todas las combinaciones hay que incluir aquellas que se les puedan agregar elementos que se neutralicen entre ellos mismos. (números simétricos)

Output

Para todas las combinaciones de 8 dado {1, 3, 5, 2 , -1, 9}

[[3, 5], [5, 2, 1], [1, 2, 5], [-1, 5, 1, 3], [-1, 3, 1, 5], [5, 1, 2], [2, 1, 5], [1, 5, -1, 3], [1, 3, -1, 5], [-1, 5, 3, 1], [-1, 1, 3, 5], [3, 5, -1, 1], [-1, 9], [-1, 3, 5, 1], [-1, 1, 5, 3], [3, 5, 1, -1], [1, 5, 3, -1], [1, 3, 5, -1], [9, -1], [2, 5, 1], [1, 5, 2], [5, 3]]

Nota: Como consideración, sería mucho más eficiente pasarle un ArrayList previamente filtrado para evitar números repetidos, y Cambiar el HashSet a ArrayList, es decir que el main se viera así:

public class Main {
    static ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>(Arrays.asList(1, 4, 5, 9 , 11, 1, 1, 1, 1));
        int search = 30;

        ...
        getNCombinations(nums.stream().distinct().collect(Collectors.toCollection(ArrayList::new)), 0, search, search);
        System.out.println(result);
        
    }
}

Answer 2

finalmente encontré dos maneras de resolver el problema. En primer lugar hay que tomar en cuenta que para obtener recursivamente las combinaciones sin repetición se necesitan dos ramas.

SOLUCIÓN 1

  public static void main(String[] args) {
       int[] array= {1, 4, 5, 9, 11};
       int target= 30;

       /*La siguiente función verifica si el array tiene al menos un grupo que 
         su suma sea igual a 'target'. Para eso hay que recurrir a combinaciones sin 
         repetición
       */

      String s= (combinaciones(0, array, target)) ? "Si" : "No";
      System.out.println(s);
    }

    private static boolean combinaciones(int index, int[] array, int objetivo) {
        if (objetivo == 0) {
            return true;
        } else if (objetivo < 0 || index >= array.length) {
            return false;
        }
        if (combinaciones(index + 1, array, objetivo)) {
            return true;
        }
        return combinaciones(index + 1, array, objetivo - array[index]);
    }

SOLUCIÓN 2 La otra solución consta de una función recuriva con for, en la que se trabaja con asignación por referencia. De esa manera, en vez de trabajar con booleanos, se asigna un valor a un array o un ArrayList. Mi versión de ese código es el siguiente:

 public static void main(String[] args) {
       Integer[] array= {1, 4, 5, 9, 11};
       int target= 30;

      String s= (existeCombinacion(array, target)) ? "Si" : "No";
      System.out.println(s);
    }

     public static boolean existeCombinacion(Integer[] array, int target) {
        ArrayList<Integer> combinations = new ArrayList<Integer>();
        Arrays.sort(array);
        int[] arr = new int[1];
        boolean b = false;
        if (array == null || array.length == 0) {
            return true;
        } else {
            combinar(new ArrayList<>(Arrays.asList(array)), combinations, target, 0, arr);
            b = (arr[0] == 1) ? true : false;
        }
        return b;
    }

public static void combinar(ArrayList<Integer> numbers, ArrayList<Integer> combinaciones, int target, int index, int[] result) {
        if (target == 0) {
            result[0] = 1;
            return;
        } else {
            for (int i = index; i < numbers.size(); ++i) {
                if (numbers.get(i) > target) {
                    break;
                } else {
                    combinaciones.add(numbers.get(i));
                    combinar(numbers, combinaciones, target - numbers.get(i), i + 1, result);
                    combinaciones.remove(combinaciones.size() - 1); // Remove the last number
                }
            }
        }
    }

EN RESUMEN

De ambas funciones se derivan dos ramas. En la primera se ve claramente con dos recursiones. En la segunda en más sutil, al eliminar un elemento luego de la recursión, de modo que cuando el puntero llegue a esa línea ejecuta la recursión sin el último valor en añadirse.