J'ai trouvé des solutions à ma question dans d'autres langues. Lorsque je les ai converties à JavaScript, cela ne créerait pas de tableau.
const find_digits = (n, sum, out, index) => {
if (index > n || sum < 0) return;
let f = "";
if (index == n) {
if (sum == 0) console.log(out); // Success!
return;
}
for (var i = 0; i < 10; i++) {
out[index] = i;
find_digits(n, sum - i, out, index + 1);
}
}
const subset_sum = (n, sum) => {
var out = [].fill(false, 0, n + 1);
for (var i = 0; i < 10; i++) {
out[0] = i;
find_digits(n, sum - i, out, 1);
}
return out;
}
console.log(subset_sum(3, 17)); // Output: [9,9,9]
4 Réponses :
const find_digits = (n, sum, out, index) => {
if (index >= n) return;
out[index] = 9;
find_digits(n, sum, out, index +1);
}
const subset_sum = (n, sum) => {
var out = [].fill(false, 0, n + 1);
find_digits(n, sum, out, 0);
return out;
}
console.log(subset_sum(3, 17));Merci pour votre réponse. Oui, c'est le problème exact que je reçois. J'ai besoin de la fonction parce que je génère des licences spéciales pour mon logiciel qui partie de la norme sera une somme des chiffres dont les chiffres égaux à S
Vous devez appeler votre fonction sans console, comme ceci: Suberset_sum (3, 17) Parce que vous écrivez à la console dans votre code. Votre problème est que votre sous-ensemble reviendra à la fin de la matrice. Donc, vous avez 2 options: - Appelez votre fonction par nom - retour à la fin du sous-ensemble_sum juste "retour"
Je pourrais rendre la récursion un peu plus explicite. À mon esprit, il existe un certain nombre de cas de base différents, pour diverses valeurs bases de Le cas récursif consiste à prendre chaque chiffre comme potentiel de premier chiffre, puis à le rejoindre avec chacun des résultats impliqués dans le recouvrement, en prenant ce montant du total et à l'aide d'un chiffre de chiffre un plus petit. P> Voici une implémentation de celle-ci: p> p> N code> et s code>:
s , il n'y a aucun résultat li>
S == 0 code>, le seul résultat est une chaîne de n code> zéros li>
n == 1 code>, puis
s , le seul résultat est le chiffre s code> li>
const subsetSum = (n, s) =>
s < 0 || (n <= 1 && s >= 10)
? []
: n == 1
? [String(s)]
: // else
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] .flatMap (
k => subsetSum (n - 1, s - k) .map (p => k + p)
)
Ajouté une mise à jour qui supprime une base de base inutile.
La fonction ci-dessous vous permet de passer dans une base / alphabet différent.
Il génère d'abord les permutations, puis filtre les résultats basés sur la valeur que vous avez transmise en tant que second paramètre. P>
.as-console-wrapper {min-height: 100% !important; top: 0}Bien que les multiples bases soient un ajout intéressant, je crains que la génération de toutes les possibilités (base) ^ (n) augmenterait beaucoup plus rapidement que le nombre réel de matches. À un moment donné, je m'attendrais à ce que cela devienne beaucoup plus cher que les autres approches ici. (Bien sûr, cela pourrait être bien au-delà du besoin de l'OP.)
@Scottsauyet J'ai essayé de rendre la fonction plus extensible et plus amusante! : P Ça fait trop cher, mais le garçon est-il optimisé.
La surpoussette est amusante, mais je m'inquiétais de la dés-optimisation ici. Depuis la grande majorité des mots de longueur-n tirés d'un alphabet / base - ils ne sont pas des permutations - ne totalisent pas notre cible, il semble y avoir beaucoup de calcul de gaspillage. Pour le (3, 17) cas décimal, il n'y a que 63 résultats, mais vous devez vérifier 1000 entrées pour les trouver, non? Je n'ai pas regardé de près le code, j'ai peur. Peut-être que je me trompe.