public class BackTracking {

    private List<Coche> resultado = new ArrayList<Coche>(); //Lista con mi resultado
    public List<Coche> recursividad(Integer indice,List<Coche> lista,Integer presupueto){

        if((indice == Test.lista.size() || presupueto == Test.presupuesto) && getPrimero(lista)){ //Cuando haya recorrido toda la lista o haya gastado todo el presupuesto

            //Obtengo la lista con mayor numero de votos
            if(resultado.size() == 0 || lista.stream().mapToDouble(x->x.getSatisfaccionClientes()).sum() > resultado.stream().mapToDouble(x->x.getSatisfaccionClientes()).sum()){
                resultado.clear(); //Elimino la lista que hubiese antes
                resultado.addAll(lista); //Añado la nueva lista
            }

       }else{
                for(Boolean a : getAlternativa(lista,indice,presupueto)){ //Las alternativas

                    if(a == true){
                        presupueto+=Test.lista.get(indice).getCoste(); //Añado
                        lista.add(Test.lista.get(indice));
                    }
                    recursividad(indice+1, lista,presupueto);
                    if(a == true){
                        presupueto-=Test.lista.get(indice).getCoste(); //Elimino
                        lista.remove(Test.lista.get(indice));
                    }
                }
        }
        return resultado;

    }

    public List<Boolean> getAlternativa(List<Coche> lista,Integer indice,Integer presupueto){
        List<Boolean> res = new ArrayList<Boolean>();
        if(indice >= 0 && indice < Test.lista.size()){
            if(presupueto + Test.lista.get(indice).getCoste() <= Test.presupuesto){
                res.add(true);
            }
            res.add(false);
        }
        return res;
    }

    //Al menos un coche de cada tipo de coche
    public Boolean getPrimero(List<Coche> lista){
            Boolean res = false;
            Integer num1= 0;
            Integer num2= 0;
            Integer num3= 0;
            Integer num4= 0;
            for(Coche a : lista){
                   if(a.getTipoCoche().equals(Coche.TipoCoche.Berlina)){
                       num1++;
                   }
                   if(a.getTipoCoche().equals(Coche.TipoCoche.Compacto)){
                       num2++;
                   }
                   if(a.getTipoCoche().equals(Coche.TipoCoche.Familiar)){
                       num3++;
                   }
                   if(a.getTipoCoche().equals(Coche.TipoCoche.Utilitario)){
                       num4++;
                   }
            }
            if(num1 >= 1 && num2 >= 1 && num3 >= 1 && num4 >= 1){
                res = true;
            }
            return res;
    }

}