comptejuste

package logbackcomptejuste;

/**
 *
 * @author Aftab
 */
public class LogBackCompteJuste {

    /**
     * @param args the command line arguments
     */
    public static boolean compteJuste(int somme, int[] disponible) {
        boolean[] dispoUtilise = new boolean[disponible.length]; // init à faux

        if (backtracking(somme, disponible, 0, dispoUtilise)) {
            return true;
        } else {
            return false;
        }
    }

    public static boolean backtracking(int somme, int[] disponible, int possede, boolean[] dispoUtilise) {

        boolean reussite = false;

        int indDispo = 0;

        while (!reussite && indDispo < disponible.length) {
            /*
             * System.out.println(indDispo); System.out.println("possède :
             * "+possede); System.out.println("dispo[ind] : "
             * +disponible[indDispo] );
             *
             */
            if (estAcceptable(somme, disponible[indDispo], possede, dispoUtilise, indDispo)) {

                possede = possede + disponible[indDispo];
                //System.out.println(" possède : "+possede);
                dispoUtilise[indDispo] = true;

                if (possede < somme) {
                    reussite = backtracking(somme, disponible, possede, dispoUtilise);

                    if (!reussite) {

                        possede = possede - disponible[indDispo];
                        dispoUtilise[indDispo] = false;

                    }

                }else{
                    reussite = true;
                }

            }

            //   System.out.println("bad");

            indDispo = indDispo + 1;
        }



        return reussite;
    }

    public static boolean estAcceptable(int somme, int valeurAjouté, int possede, boolean[] dispoUtilise, int indDispo) {
        //  System.out.println("somme , valeurAjoute , possède : " + somme + " " + valeurAjouté+" "+possede);
        // System.out.println("valeur ajouté :" + (possede + valeurAjouté));

        boolean accpte = false;

        if (!dispoUtilise[indDispo]) {
            if (somme >= (possede + valeurAjouté)) {
                //System.out.println("trueOK : "+ possede + valeurAjouté);
                accpte = true;
            } else {
                accpte = false;
            }
        }
        //System.out.println(accpte);
        return accpte;

    }

    public static void main(String[] args) {
        // TODO code application logic here
        int[] disponible = {10, 20, 50, 30};
        int somme = 0;

        System.out.println(compteJuste(somme, disponible));

    }
}