Algorithme de partition sans boucle, seule récursivité

Question

Étant donné une liste d'entiers. Découvrez s'il peut être divisé en deux sous-listes avec une somme égale. Les numéros de la liste ne sont pas triés.

Par exemple:
Une liste comme [1, 2, 3, 4, 6] retourne vrai, parce que 2 + 6 = 1 + 3 + 4 = 8
Une liste similaire [2, 1, 8 , 3] retournera faux. J'ai vu ce problème dans une plateforme de pratique en ligne. Je sais comment faire avec loop + récursion, mais comment le résoudre sans boucle (ou itérateur)?

Answer 1

La façon de penser à cela pour essayer de penser de quelle façon vous pouvez diviser ce problème en petits problèmes qui dépendent les uns des autres. La première chose qui vient à l'esprit est de diviser le problème en fonction de l'indice. Essayons d'aller de gauche à droite (augmenter l'index de 1 à chaque appel). Notre cas de base serait après que nous ayons traversé tous les éléments, c'est-à-dire la fin du tableau. Que devons-nous faire là-bas? Comparez les sommes les unes avec les autres, nous devons donc les passer en revue. Pour l'appel récursif réel, il y a 2 possibilités, celles-ci étant l'élément courant ajouté à l'une ou l'autre somme. Nous avons juste besoin de vérifier ces deux appels et de retourner true si un retourné true.

---

Cela conduit à une solution sans boucles en ayant votre fonction récursive prendre l'indice courant ainsi que les sommes en tant que paramètres, et ayant 2 cas récursives - un où vous ajoutez l'élément courant à une somme , et un où vous l'ajoutez à l'autre somme. Et comparez ensuite les sommes lorsque vous arrivez à la fin du tableau.

En Java, il ressemblerait à ceci:

boolean canBeDividedEqually(int[] array) 
{ 
    return canBeDividedEquallyHelper(array, 0, 0, 0); 
} 

boolean canBeDividedEquallyHelper(int[] array, int i, int sum1, int sum2) 
{ 
    if (i == array.length) 
     return sum1 == sum2; 
    return canBeDividedEquallyHelper(array, i+1, sum1 + array[i], sum2) || 
      canBeDividedEquallyHelper(array, i+1, sum1, sum2 + array[i]); 
} 

Cela peut être amélioré légèrement seulement en passant par 1 somme et soit en ajoutant ou soustrayant, puis à comparer contre 0 à la fin. Notez que ceci est the partition problem et que cette solution de force brute prend un temps exponentiel (c'est-à-dire qu'elle devient très lente très rapidement lorsque la taille d'entrée augmente).