public class BackTracking {

    /**
     * Ejercicio posibles combinaciones usando backTracking
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int lista[] = {1,1,1,11,5,1};
        int X[] = getMatrizCero(lista.length);
        int M = 0;
        int r = 0;
        comb(lista,M,X,r);
        if(contador ==0 ){
            System.out.println("No existen combinaciones");
        }
    }
    static int contador=0;
    public static void comb(int list[],int M,int x[], int r){   
        while(r<list.length){ //si r excede el tamaño acaba el metodo
            x[r]= 1;
            if(suma(x,list)==M){
                contador++;
                System.out.println(print(sacaDato(x,list))); //si la combinacion es correcta se imprime           
            }else{
                if(suma(x,list)<M){       
                    comb(list,M,x,r+1);// al ser menor se agrega el siguiente elemento                 
                }
            }
            x[r]=0;// se iguala a 0 y se prueba con la siguiente opcion
            r++;
        }
    }
    public static int suma(int x[],int l[]){
        int suma = 0;
        for(int i = 0; i<x.length; i++){
            suma = (x[i]*l[i])+suma;                    
        }
        return suma;
    }
    public static String print(int []x ){
        String nuevo =""+x[0];
        for(int i = 1; i<x.length;i++){
            nuevo = nuevo+" - "+x[i];
                    
        }
        return nuevo;
    }
    public static int[] sacaDato(int[] x, int[]l){
        int[] copia = new int[x.length];
        for(int i = 0; i<x.length; i++){
            copia[i] = x[i]*l[i];
        }
        return copia;
    }
   
private static int[] getMatrizCero(int l) {
     int [] aux = new int[l];
  for(int i=0;i<l;i++) aux[i] = 0;
  return aux;
 }
}