Retourne tous les sous-ensembles dont la somme est une valeur donnée (problème de la somme des sous-ensembles)

Question

Le problème de la somme des sous-ensembles est le problème de créer un algorithme qui prend un tableau et une somme et renvoie tous les sous-ensembles du tableau d'arguments dont la somme est égale à la somme donnée. J'essaie de résoudre une variante du problème de la somme des sous-ensembles (en utilisant JavaScript) dans laquelle seuls les entiers non négatifs sont autorisés et où tous les sous-ensembles dont la somme est égale à la somme passée en argument sont renvoyés.

J'ai suivi une approche de programmation dynamique pour résoudre le problème et j'ai créé une fonction qui renvoie un tableau booléen bidimensionnel montrant quels sous-ensembles du tableau d'arguments ont une somme égale à la somme donnée. Chaque ligne représente un nombre dans le tableau d'arguments (la première ligne représente le premier élément, la deuxième ligne représente le deuxième élément, etc.); et chaque colonne représente une valeur de somme (la colonne la plus à gauche représente somme = 0 et la colonne la plus à droite représente la somme = "somme d'argument"). Si l'élément subsetArray[r][c] == true, alors le sous-ensemble {array[0], array[1], ..., array[r]} a des éléments qui s'additionnent à "c".

const subsetSum = (array, sum) => {
   // Initialiser un tableau booléen 2D vide.
   let subsetArray = new Array(array.length)
      .fill(false)
      .map(() => new Array(sum + 1).fill(false));

   for (let e = 0; e < array.length; e++) {
      for (let s = 0; s <= sum; s++) {
         if (s === 0 || s === array[e]) {
            subsetArray[e][s] = true;
            continue;
         }
         if (e > 0) {
            if (
               subsetArray[e - 1][s] === true ||
               subsetArray[e - 1][s - array[e]] === true
            ) {
               subsetArray[e][s] = true;
            }
         }
      }
   }
   return subsetArray;
};

Remarque: Cette fonction ne résout pas le problème. Elle fournit uniquement les sous-ensembles qui sont garantis d'inclure des sous-ensembles dont la somme est égale à la somme spécifiée.

Mon problème est que j'ai besoin d'extraire les sous-ensembles réels dont la somme est égale à la somme spécifiée de ce tableau booléen. J'ai essayé de le faire, mais la logique de mon approche (qui implique d'utiliser le tableau booléen pour réduire le nombre de sous-ensembles à analyser) devient plutôt compliquée et j'ai du mal à la mettre en œuvre.

Est-ce que quelqu'un connaît une bonne méthode pour trouver tous les sous-ensembles dont la somme est égale à la somme donnée lorsque l'on a le tableau booléen généré par subsetSum ?

Edit 1

Entrée

Somme: 17
Tableau : 7 2 1 5 1 20 7

Sortie

7 7 2 1

Answer 1

Vous pourriez adopter une approche itérative et récursive pour trouver des sommes de sous-ensembles.

Cette approche retourne deux ensembles, en raison des doubles.

Cela fonctionne en prenant des valeurs de l'array ou non.

Dans l'en-tête de la fonction, plusieurs vérifications sont effectuées. La première vérifie si la somme est atteinte par tous les éléments dans l'array temporaire t. Si la somme voulue est atteinte, l'array temporaire est ajouté à l'ensemble de résultats.

Si l'indice a la valeur de la longueur de l'array, la récursion s'arrête.

La dernière vérification regarde en avant et si la somme est inférieure ou égale à la somme cible, l'élément à l'indice actuel i est pris pour la prochaine récursion.

Le dernier appel de fork omet l'élément actuel et continue avec l'indice suivant.

tl;dr

Prenez soit un élément, construisez la somme ou omettez l'élément. Puis passez à l'indice suivant.

Un exemple de nombres pris :

7
7 2
7 2 1
7 2 1 5
7 2 1 5 1
7 2 1 5 1
7 2 1 5 1
7 2 1 5
...
7
7 7
7

2
2 1
2 1 5
2 1 5 1
...
2
2 7
2

1
1 5
1 5 1
1 5 1
...
1
1 7
1

5
5 1
5 1
...
5
5 7
5

1
1
...
1
1 7
1

7

function getSubsets(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            result.push(t);
            return;
        }
        if (i === array.length) {
            return;
        }
        if (s + array[i] <= sum) { // short circuit for positive numbers only
            fork(i + 1, s + array[i], t.concat(array[i]));
        }
        fork(i + 1, s, t);
    }

    var result = [];
    fork();
    return result;
}

console.log(getSubsets([7, 2, 1, 5, 1, 20, 7], 17));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Si vous le souhaitez, vous pourriez utiliser une fonction génératrice avec un paramètre supplémentaire pour l'ensemble de résultats temporaire.

function* subsets(values, sum, parts = []) {
    var i, s;

    for (i = 0; i < values.length; i++) {
        s = sum - values[i];
        if (!s) {
            yield [...parts, values[i]];
        } else if (s > 0) {
            yield* subsets(values.slice(i + 1), s, [...parts, values[i]]);
        }
    }
}

console.log([...subsets([7, 2, 1, 5, 1, 20, 7], 17)]);

.as-console-wrapper { max-height: 100% !important; top: 0; }