public class Pieces {
  // affiche une solution...
  public static void affiche(int []essai,
                             int []valeursFaciales) {
    for (int i=0; i<essai.length; i++) {
      if (essai[i]!=0) 
        System.out.print(essai[i]+"x"+valeursFaciales[i]+" + ");
    }
    System.out.println();
  }
  // une solution est-elle correcte ? ie: la somme correspondante est-elle égale à
  // la somme cherchée ?
  public static boolean correct(int []essai,
                                int []valeursFaciales,
                                int sommeAAtteindre) {
    int sommeEssai = 0;
    for (int i=0; i<essai.length; i++) {
      sommeEssai += valeursFaciales[i]*essai[i];
    }
    return sommeEssai==sommeAAtteindre;
  }
  // compteurs divers
  public static int compteur;
  public static int solutions;

  // exploration exhaustive, ie qui teste toutes les possibilités y compris les
  // plus absurdes
  public static void explore(int type,int []valeurs,int []essai,int somme,
                             int []nombre) {
    compteur++; // un essai de plus
    if (type==valeurs.length) { // si on a fini de fabriquer une solution potentielle
      if (correct(essai,valeurs,somme)) { // on teste si c'est une solution correcte
        solutions++; // une solution correcte de plus
        affiche(essai,valeurs); // on l'affiche
      }
      return; // dans tous les cas (bonne ou pas bonne) on revient à une évenutelle possibilité suivante
    }
    // On essaie toutes les possibilités pour une valeur faciale donnée, donc
    // toutes les combinaisons qui font apparaître de 0 au nombre d'exemplaires
    // possible pour cette pièce.
    for (int choix=0; choix<=nombre[type]; choix++) {
      essai[type] = choix; // on effectue un choix
      explore(type+1,valeurs,essai,somme,nombre); // on essaie de complémenter la solution partielle
    }
  }

  // le même algorithme avec rebroussement (backtracking)
  // il y a un argumehnt de plus qui correspond à la somme déjà accumulée au fur
  // et à mesure de la construction de la solution...
  public static void explore2(int type,int []valeurs,int []essai,int somme,
                              int []nombre,int accumulation) {
    compteur++; // un test de plus
    if (accumulation>somme) return; // on coupe l'exploration à ce niveau car on a déjà dépassé notre but, inutile de rajouter des pièces
    if (type==valeurs.length) { // si on est arrivé à construire une solution complète
      // if (correct(essai,valeurs,somme)) {
      if (accumulation==somme) { // et que la somme accumulée correspond au but fixé
        solutions++; // une solution de plus
        affiche(essai,valeurs); // que l'on affiche
      }
      return; // dans tous les cas, on revient à un choix précédent pour passer à un éventuel choix suivant
    }
    // on essaie toutes les possibilités pour la valeur faciale courante
    for (int choix=0; choix<=nombre[type]; choix++) {
      essai[type] = choix; // on enregistre le choix
      explore2(type+1,valeurs,essai,somme,nombre,accumulation+choix*valeurs[type]); // on accumule la somme correspondant au choix que l'on vient de faire
    }
  }
  
  public static void main(String []a) {
    // valeurs faciales
    int []valeurs = { 1, 2, 5, 7, 13 };
    // exemplaires disponibles
    int []nombre = { 7, 2, 0, 1, 20 };
    // essai (au début ne contient rien)
    int []essai = new int[nombre.length];

    // somme à atteindre (faire joujou avec la valeur)
    int somme = 278;

    System.out.println("Exploration complete");
    compteur = 0; solutions = 0;
    explore(0,valeurs,essai,somme,nombre);
    System.out.println("J'ai exploré "+compteur+" solutions et j'en ai trouvé "+solutions);
    
    System.out.println("avec rebroussement");
    compteur = 0; solutions = 0;
    explore2(0,valeurs,essai,somme,nombre,0);
    System.out.println("J'ai exploré "+compteur+" solutions et j'en ai trouvé "+solutions);
  }
}