public class BackTrackin {

    private static int cont=0;
 /**
     * 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 = 10;
        int r = 0;
        comb(lista,M,X,r);
        if(cont==0) System.out.println("No hay combinaciones posibles.");
    }
    private static int[] getMatrizCero(int l) {
     int [] aux = new int[l];
  for(int i=0;i<l;i++) aux[i] = 0;
  return aux;
 }
    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;
            cont++;
            if(suma(x,list)==M){
                System.out.println(print(sacaDato(x,list))); //si la combinacion es correcta se imprime
           //se iguala a cero el ultimo elemento para probar con otras combinaciones
            }else{
              if(suma(x,list)>M){
                     x[r] = 0;
                     cont--;//al ser mayor se elimina el elemento para luego probar con el siguiente            
                 }else{
                  cont--;
                     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;
    }
}