Trouver toutes les combinaisons possibles de nombres pour atteindre une somme donnée

232

Comment feriez-vous pour tester toutes les combinaisons possibles d'additions à partir d'un ensemble donné Nde nombres afin qu'ils s'additionnent à un nombre final donné?

Un bref exemple:

  • Ensemble de nombres à ajouter: N = {1,5,22,15,0,...}
  • Résultat désiré: 12345
James P.
la source
@James - Je pense que votre problème doit être clarifié. Quelles sont les règles? Pouvez-vous choisir n'importe quel nombre? Quels numéros sont dans l'ensemble? Quelles sont vos contraintes?
jmort253
9
L'article de wikipedia ( en.wikipedia.org/wiki/Subset_sum_problem ) mentionne même que ce problème est une bonne introduction à la classe des problèmes NP-complets.
user57368
1
@ jmort253: Je ne pense pas qu'il y ait d'autres contraintes que d'avoir un ensemble d'entiers positifs et inférieurs au nombre donné comme cible. Toute combinaison de chiffres peut être utilisée. Ce ne sont pas des devoirs, mais le genre de problème que vous devrez résoudre si vous postulez pour certains emplois. Je peux généralement imaginer un algorithme en cas de besoin, mais je ne sais pas comment afficher quelque chose comme ça. Il doit être décomposé en quelque sorte (récursif?).
James P.
3
@James, Avez-vous besoin des combinaisons ou simplement du nombre de sous-ensembles qui s'ajoutent à la somme?
st0le
6
Pouvons-nous utiliser le même élément de l'ensemble d'origine plus d'une fois? Par exemple, si l'entrée est {1,2,3,5} et la cible 10, 5 + 5 = 10 est-il une solution acceptable?
alampada

Réponses:

248

Ce problème peut être résolu avec une combinaison récursive de toutes les sommes possibles filtrant celles qui atteignent la cible. Voici l'algorithme en Python:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Ce type d'algorithmes est très bien expliqué dans la conférence suivante de programmation abstraite de Standford - cette vidéo est très recommandable pour comprendre comment fonctionne la récursivité pour générer des permutations de solutions.

Éditer

Ce qui précède en tant que fonction de générateur, ce qui le rend un peu plus utile. Nécessite Python 3.3+ à cause de yield from.

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Voici la version Java du même algorithme:

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

C'est exactement la même heuristique. Mon Java est un peu rouillé mais je pense qu'il est facile à comprendre.

Conversion C # de la solution Java: (par @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Solution Ruby: (par @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit: discussion de complexité

Comme d'autres le mentionnent, c'est un problème NP-difficile . Il peut être résolu en temps exponentiel O (2 ^ n), par exemple pour n = 10 il y aura 1024 solutions possibles. Si les cibles que vous essayez d'atteindre sont dans une fourchette basse, alors cet algorithme fonctionne. Ainsi, par exemple:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) génère 1024 branches car la cible ne parvient jamais à filtrer les solutions possibles.

En revanche, subset_sum([1,2,3,4,5,6,7,8,9,10],10)ne génère que 175 branches, car la cible à atteindre 10doit filtrer de nombreuses combinaisons.

Si Net Targetsont de grands nombres, on devrait passer à une version approximative de la solution.

Manuel Salvadores
la source
1
Optimisation Java: ArrayList <Integer> partial_rec = new ArrayList <Integer> (partial); partial_rec.add (n); cela fait une copie de partielle. et ajoute ainsi O (N). Une meilleure façon est de simplement "partial.add (n)" faire la récursivité puis "partial.remove (partial.size -1). J'ai réanalysé votre code pour vous en assurer. Cela fonctionne très bien
Christian Bongiorno
4
Cette solution ne fonctionne pas dans tous les cas. Considérez [1, 2, 0, 6, -3, 3], 3- il ne sort [1,2], [0,3], [3]que lorsque des cas manquants tels que[6, -3, 3]
LiraNuna
11
Il ne fonctionne pas pour toutes les combinaisons, par exemple [1, 2, 5], 5seulement les sorties [5], quand [1, 1, 1, 1, 1], [2, 2, 1]et [2, 1, 1, 1]sont des solutions.
cbrad
3
@cbrad c'est à cause de i+1in remaining = numbers[i+1:]. Il semble que cet algorithme n'autorise pas les doublons.
Leonid Vasilev
1
@cbrad Pour obtenir également des solutions comprenant des doublons comme [1, 1, 3]jetez un œil à stackoverflow.com/a/34971783/3684296 (Python)
Mesa
36

La solution de ce problème a été donnée un million de fois sur Internet. Le problème est appelé le problème de changement de pièce . On peut trouver des solutions sur http://rosettacode.org/wiki/Count_the_coins et un modèle mathématique de celui-ci sur http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (ou changement de pièce Google problème ).

Soit dit en passant, la solution Scala de Tsagadai est intéressante. Cet exemple produit 1 ou 0. Comme effet secondaire, il répertorie sur la console toutes les solutions possibles. Il affiche la solution, mais échoue à la rendre utilisable de quelque manière que ce soit.

Pour être le plus utile possible, le code doit renvoyer un List[List[Int]]afin de permettre d'obtenir le nombre de solutions (longueur de la liste des listes), la "meilleure" solution (la liste la plus courte), ou toutes les solutions possibles.

Voici un exemple. C'est très inefficace, mais c'est facile à comprendre.

object Sum extends App {

  def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {

    def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
      (x._1 + y._1, x._2 ::: y._2)
    }

    def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
      if (numbers.isEmpty || total < 0) {
        (0, resultAcc)
      } else if (total == 0) {
        (1, sumAcc :: resultAcc)
      } else {
        add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
      }
    }

    sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
  }

  println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}

Lorsqu'il est exécuté, il affiche:

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)

La sumCombinations()fonction peut être utilisée seule et le résultat peut être analysé plus en détail pour afficher la «meilleure» solution (la liste la plus courte) ou le nombre de solutions (le nombre de listes).

Notez que même ainsi, les exigences peuvent ne pas être entièrement satisfaites. Il peut arriver que l'ordre de chaque liste dans la solution soit significatif. Dans un tel cas, chaque liste devrait être dupliquée autant de fois qu'il y a de combinaison de ses éléments. Ou nous pourrions être intéressés uniquement par les combinaisons qui sont différentes.

Par exemple, nous pourrions considérer que cela List(5, 10)devrait donner deux combinaisons: List(5, 10)et List(10, 5). Car List(5, 5, 5)il pourrait donner trois combinaisons ou une seule, selon les besoins. Pour les entiers, les trois permutations sont équivalentes, mais si nous avons affaire à des pièces, comme dans le "problème de changement de pièces", elles ne le sont pas.

Il n'est pas non plus indiqué dans les exigences la question de savoir si chaque numéro (ou pièce) ne peut être utilisé qu'une ou plusieurs fois. Nous pourrions (et nous devrions!) Généraliser le problème à une liste de listes d'occurrences de chaque nombre. Cela se traduit dans la vie réelle par "quelles sont les façons possibles de gagner une certaine somme d'argent avec un ensemble de pièces (et non un ensemble de valeurs de pièces)". Le problème d'origine n'est qu'un cas particulier de celui-ci, où nous avons autant d'occurrences de chaque pièce que nécessaire pour faire le montant total avec chaque valeur de pièce unique.

Pierre-Yves Saumont
la source
14
Ce problème n'est pas exactement le même que le problème de changement de pièce. OP demande toutes les combinaisons, pas seulement le minimum. Et, vraisemblablement, les entiers de l'ensemble peuvent être négatifs. Par conséquent, certaines optimisations du problème de changement de pièces ne sont pas possibles avec ce problème.
ThomasMcLeod
5
et aussi ce problème permet la répétition des éléments, je ne suis pas sûr que OP le voulait, mais plus un problème de sac à dos
caub
34

À Haskell :

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

Et J :

(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...

Comme vous pouvez le remarquer, les deux adoptent la même approche et divisent le problème en deux parties: générer chaque membre de l'ensemble de puissance et vérifier la somme de chaque membre à la cible.

Il existe d'autres solutions, mais c'est la plus simple.

Avez-vous besoin d'aide pour l'une ou l'autre ou pour trouver une approche différente?

éphémère
la source
3
Wow, c'est un code assez concis. Je suis d'accord avec votre réponse. Je pense que j'ai juste besoin de lire un peu sur les algorithmes en général. Je vais jeter un œil à la syntaxe des deux langues car vous avez éveillé ma curiosité.
James P.
Je viens d'installer Haskell pour essayer cela, je ne peux certainement pas simplement le coller et le faire exécuter, not in scope: 'subsequences'des pointeurs?
Hart CO
4
@HartCO un peu tard pour la fête, maisimport Data.List
Jir
28

Une version Javascript:

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target) {
    return;  // if we reach the number why bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([3,9,8,4,5,7,10],15);

// output:
// 3+8+4=15
// 3+5+7=15
// 8+7=15
// 5+10=15

rbarilani
la source
Le code a une erreur dans la tranche, devrait être remaining = numbers.slice(); remaining.slice(i + 1);autrement numbers.slice(i + 1);change le tableau des nombres
Emeeus
@Emeeus, je ne pense pas que ce soit vrai. slicerenvoie une copie (superficielle), il ne modifie pas le numberstableau.
Dario Seidl
@DarioSeidl oui, slice renvoie une copie, elle ne modifie pas le tableau, c'est le point, c'est pourquoi si vous ne l'assignez pas dans une variable vous ne la changez pas. Dans ce cas, si je comprends bien, nous devons passer une version modifiée, pas l'original. Voir ce jsfiddle.net/che06t3w/1
Emeeus
1
@Redu ... par exemple, un moyen facile de le faire est que nous pouvons légèrement modifier l'algorithme et utiliser une fonction interne: jsbin.com/lecokaw/edit?js,console
rbarilani
1
Le code donné n'obtient pas nécessairement toutes les combinaisons. Par exemple, mettre [1,2], 3 ne renverra que 1 + 2 = 3 et non 1 + 1 + 1 ou 2 + 1
JuicY_Burrito
12

Version C ++ du même algorithme

#include <iostream>
#include <list>
void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial)
{
        int s = 0;
        for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
        {
            s += *cit;
        }
        if(s == target)
        {
                std::cout << "sum([";

                for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
                {
                    std::cout << *cit << ",";
                }
                std::cout << "])=" << target << std::endl;
        }
        if(s >= target)
            return;
        int n;
        for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
        {
            n = *ai;
            std::list<int> remaining;
            for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
            {
                if(aj == ai)continue;
                remaining.push_back(*aj);
            }
            std::list<int> partial_rec=partial;
            partial_rec.push_back(n);
            subset_sum_recursive(remaining,target,partial_rec);

        }
}

void subset_sum(std::list<int> numbers,int target)
{
    subset_sum_recursive(numbers,target,std::list<int>());
}
int main()
{
    std::list<int> a;
    a.push_back (3); a.push_back (9); a.push_back (8);
    a.push_back (4);
    a.push_back (5);
    a.push_back (7);
    a.push_back (10);
    int n = 15;
    //std::cin >> n;
    subset_sum(a, n);
    return 0;
}
smac89
la source
11

Version C # de la réponse du code @msalvadores

void Main()
{
    int[] numbers = {3,9,8,4,5,7,10};
    int target = 15;
    sum_up(new List<int>(numbers.ToList()),target);
}

static void sum_up_recursive(List<int> numbers, int target, List<int> part)
{
   int s = 0;
   foreach (int x in part)
   {
       s += x;
   }
   if (s == target)
   {
        Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target);
   }
   if (s >= target)
   {
        return;
   }
   for (int i = 0;i < numbers.Count;i++)
   {
         var remaining = new List<int>();
         int n = numbers[i];
         for (int j = i + 1; j < numbers.Count;j++)
         {
             remaining.Add(numbers[j]);
         }
         var part_rec = new List<int>(part);
         part_rec.Add(n);
         sum_up_recursive(remaining,target,part_rec);
   }
}
static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers,target,new List<int>());
}
smac89
la source
4

Je pensais que j'utiliserais une réponse à cette question mais je ne pouvais pas, alors voici ma réponse. Il utilise une version modifiée d'une réponse dans Structure et interprétation des programmes informatiques . Je pense que c'est une meilleure solution récursive et devrait plaire davantage aux puristes.

Ma réponse est en Scala (et je m'excuse si mon Scala est nul, je viens de commencer à l'apprendre). La folie de findSumCombinations est de trier et unique la liste originale pour la récursivité pour éviter les dupes.

def findSumCombinations(target: Int, numbers: List[Int]): Int = {
  cc(target, numbers.distinct.sortWith(_ < _), List())
}

def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = {
  if (target == 0) {println(solution); 1 }
  else if (target < 0 || numbers.length == 0) 0
  else 
    cc(target, numbers.tail, solution) 
    + cc(target - numbers.head, numbers, numbers.head :: solution)
}

Pour l'utiliser:

 > findSumCombinations(12345, List(1,5,22,15,0,..))
 * Prints a whole heap of lists that will sum to the target *
Tsagadai
la source
4
Thank you.. ephemient

j'ai converti la logique ci-dessus de python en php ..

<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;

print_r(bestsum($data,$maxsum));  //function call

function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array();              //base case
foreach($data as $group)
{
 $new_res = $res;               //copy res

  foreach($group as $ele)
  {
    for($i=0;$i<($maxsum-$ele+1);$i++)
    {   
        if($res[$i] != 0)
        {
            $ele_index = $i+$ele;
            $new_res[$ele_index] = $res[$i];
            $new_res[$ele_index][] = $ele;
        }
    }
  }

  $res = $new_res;
}

 for($i=$maxsum;$i>0;$i--)
  {
    if($res[$i]!=0)
    {
        return $res[$i];
        break;
    }
  }
return array();
}
?>
bala
la source
4

Une autre solution python serait d'utiliser le itertools.combinationsmodule comme suit:

#!/usr/local/bin/python

from itertools import combinations

def find_sum_in_list(numbers, target):
    results = []
    for x in range(len(numbers)):
        results.extend(
            [   
                combo for combo in combinations(numbers ,x)  
                    if sum(combo) == target
            ]   
        )   

    print results

if __name__ == "__main__":
    find_sum_in_list([3,9,8,4,5,7,10], 15)

Production: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]

brainasium
la source
cela ne fonctionne pas, par exemple: find_sum_in_list (range (0,8), 4). Trouvé: [(4,), (0, 4), (1, 3), (0, 1, 3)]. Mais (2, 2) est également une option!
Andre Araujo
@AndreAraujo: cela n'a aucun sens d'utiliser 0, mais si vous utilisez (1,8), itertools.combinations_with_replacement fonctionne et génère également 2,2.
Rubenisme
@Rubenisme Oui, mec! Le problème était le remplacement! Merci! ;-)
Andre Araujo
4

Voici une solution dans R

subset_sum = function(numbers,target,partial=0){
  if(any(is.na(partial))) return()
  s = sum(partial)
  if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
  if(s > target) return()
  for( i in seq_along(numbers)){
    n = numbers[i]
    remaining = numbers[(i+1):length(numbers)]
    subset_sum(remaining,target,c(partial,n))
  }
}
marque
la source
Je cherche une solution dans R, mais celle-ci ne fonctionne pas pour moi. Par exemple, subset_sum(numbers = c(1:2), target = 5)renvoie "sum(1+2+2)=5". Mais la combinaison 1 + 1 + 1 + 1 + 1 est manquante. Fixer des cibles à des nombres plus élevés (par exemple 20) manque encore plus de combinaisons.
Frederick
Ce que vous décrivez n'est pas ce que la fonction est censée renvoyer. Regardez la réponse acceptée. Le fait que 2 soit répété deux fois est un artefact de la façon dont R génère et sous-ensemble les séries, et non le comportement prévu.
Mark
subset_sum(1:2, 4)ne devrait retourner aucune solution car il n'y a pas de combinaison de 1 et 2 qui ajoute à 4. Ce qui doit être ajouté à ma fonction est une fuite si iest supérieure à la longueur denumbers
Mark
3

Voici une version Java qui convient bien aux petits N et aux très grandes sommes cibles, lorsque la complexité O(t*N)(la solution dynamique) est supérieure à l'algorithme exponentiel. Ma version utilise une rencontre dans l'attaque du milieu, avec un peu de décalage afin de réduire la complexité du classique naïf O(n*2^n)auO(2^(n/2)) .

Si vous souhaitez l'utiliser pour des ensembles comprenant entre 32 et 64 éléments, vous devez changer le intqui représente le sous-ensemble actuel dans la fonction pas à un longbien que les performances diminuent de manière drastique à mesure que la taille de l'ensemble augmente. Si vous souhaitez l'utiliser pour un ensemble avec un nombre impair d'éléments, vous devez ajouter un 0 à l'ensemble pour le rendre pair.

import java.util.ArrayList;
import java.util.List;

public class SubsetSumMiddleAttack {
    static final int target = 100000000;
    static final int[] set = new int[]{ ... };

    static List<Subset> evens = new ArrayList<>();
    static List<Subset> odds = new ArrayList<>();

    static int[][] split(int[] superSet) {
        int[][] ret = new int[2][superSet.length / 2]; 

        for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];

        return ret;
    }

    static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
        accumulator.add(new Subset(subset, sum));
        if (counter != superSet.length) {
            step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
            step(superSet, accumulator, subset, sum, counter + 1);
        }
    }

    static void printSubset(Subset e, Subset o) {
        String ret = "";
        for (int i = 0; i < 32; i++) {
            if (i % 2 == 0) {
                if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
            else {
                if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
        }
        if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
        System.out.println(ret);
    }

    public static void main(String[] args) {
        int[][] superSets = split(set);

        step(superSets[0], evens, 0,0,0);
        step(superSets[1], odds, 0,0,0);

        for (Subset e : evens) {
            for (Subset o : odds) {
                if (e.sum + o.sum == target) printSubset(e, o);
            }
        }
    }
}

class Subset {
    int subset;
    int sum;

    Subset(int subset, int sum) {
        this.subset = subset;
        this.sum = sum;
    }
}
jimpudar
la source
3

Ceci est similaire à un problème de changement de pièce

public class CoinCount 
{   
public static void main(String[] args)
{
    int[] coins={1,4,6,2,3,5};
    int count=0;

    for (int i=0;i<coins.length;i++)
    {
        count=count+Count(9,coins,i,0);
    }
    System.out.println(count);
}

public static int Count(int Sum,int[] coins,int index,int curSum)
{
    int count=0;

    if (index>=coins.length)
        return 0;

    int sumNow=curSum+coins[index];
    if (sumNow>Sum)
        return 0;
    if (sumNow==Sum)
        return 1;

    for (int i= index+1;i<coins.length;i++)
        count+=Count(Sum,coins,i,sumNow);

    return count;       
}
}
DJ '
la source
2

Algorithme très efficace utilisant des tables que j'ai écrites en couple c ++ il y a quelques années.

Si vous définissez PRINT 1, il imprimera toutes les combinaisons (mais il ne sera pas utilisé la méthode efficace).

Son si efficace qu'il calcule plus de 10 ^ 14 combinaisons en moins de 10 ms.

#include <stdio.h>
#include <stdlib.h>
//#include "CTime.h"

#define SUM 300
#define MAXNUMsSIZE 30

#define PRINT 0


long long CountAddToSum(int,int[],int,const int[],int);
void printr(const int[], int);
long long table1[SUM][MAXNUMsSIZE];

int main()
{
    int Nums[]={3,4,5,6,7,9,13,11,12,13,22,35,17,14,18,23,33,54};
    int sum=SUM;
    int size=sizeof(Nums)/sizeof(int);
    int i,j,a[]={0};
    long long N=0;
    //CTime timer1;

    for(i=0;i<SUM;++i) 
        for(j=0;j<MAXNUMsSIZE;++j) 
            table1[i][j]=-1;

    N = CountAddToSum(sum,Nums,size,a,0); //algorithm
    //timer1.Get_Passd();

    //printf("\nN=%lld time=%.1f ms\n", N,timer1.Get_Passd());
    printf("\nN=%lld \n", N);
    getchar();
    return 1;
}

long long CountAddToSum(int s, int arr[],int arrsize, const int r[],int rsize)
{
    static int totalmem=0, maxmem=0;
    int i,*rnew;
    long long result1=0,result2=0;

    if(s<0) return 0;
    if (table1[s][arrsize]>0 && PRINT==0) return table1[s][arrsize];
    if(s==0)
    {
        if(PRINT) printr(r, rsize);
        return 1;
    }
    if(arrsize==0) return 0;

    //else
    rnew=(int*)malloc((rsize+1)*sizeof(int));

    for(i=0;i<rsize;++i) rnew[i]=r[i]; 
    rnew[rsize]=arr[arrsize-1];

    result1 =  CountAddToSum(s,arr,arrsize-1,rnew,rsize);
    result2 =  CountAddToSum(s-arr[arrsize-1],arr,arrsize,rnew,rsize+1);
    table1[s][arrsize]=result1+result2;
    free(rnew);

    return result1+result2;

}

void printr(const int r[], int rsize)
{
    int lastr=r[0],count=0,i;
    for(i=0; i<rsize;++i) 
    {
        if(r[i]==lastr)
            count++;
        else
        {
            printf(" %d*%d ",count,lastr);
            lastr=r[i];
            count=1;
        }
    }
    if(r[i-1]==lastr) printf(" %d*%d ",count,lastr);

    printf("\n");

}
Mendi Barel
la source
salut! J'ai besoin d'un code pour faire quelque chose comme ça, trouver toutes les sommes possibles d'ensembles de 6 nombres dans une liste de 60 nombres. Les sommes doivent être comprises entre min 180 et max 191. Ce code pourrait-il être ajusté pour cela? Où exécuter ce code sur le cloud? J'ai essayé sans succès à Codenvy
defreturn
2

Version Excel VBA ci-dessous. J'avais besoin de l'implémenter dans VBA (pas ma préférence, ne me jugez pas!), Et j'ai utilisé les réponses sur cette page pour l'approche. Je télécharge au cas où d'autres auraient également besoin d'une version VBA.

Option Explicit

Public Sub SumTarget()
    Dim numbers(0 To 6)  As Long
    Dim target As Long

    target = 15
    numbers(0) = 3: numbers(1) = 9: numbers(2) = 8: numbers(3) = 4: numbers(4) = 5
    numbers(5) = 7: numbers(6) = 10

    Call SumUpTarget(numbers, target)
End Sub

Public Sub SumUpTarget(numbers() As Long, target As Long)
    Dim part() As Long
    Call SumUpRecursive(numbers, target, part)
End Sub

Private Sub SumUpRecursive(numbers() As Long, target As Long, part() As Long)

    Dim s As Long, i As Long, j As Long, num As Long
    Dim remaining() As Long, partRec() As Long
    s = SumArray(part)

    If s = target Then Debug.Print "SUM ( " & ArrayToString(part) & " ) = " & target
    If s >= target Then Exit Sub

    If (Not Not numbers) <> 0 Then
        For i = 0 To UBound(numbers)
            Erase remaining()
            num = numbers(i)
            For j = i + 1 To UBound(numbers)
                AddToArray remaining, numbers(j)
            Next j
            Erase partRec()
            CopyArray partRec, part
            AddToArray partRec, num
            SumUpRecursive remaining, target, partRec
        Next i
    End If

End Sub

Private Function ArrayToString(x() As Long) As String
    Dim n As Long, result As String
    result = "{" & x(n)
    For n = LBound(x) + 1 To UBound(x)
        result = result & "," & x(n)
    Next n
    result = result & "}"
    ArrayToString = result
End Function

Private Function SumArray(x() As Long) As Long
    Dim n As Long
    SumArray = 0
    If (Not Not x) <> 0 Then
        For n = LBound(x) To UBound(x)
            SumArray = SumArray + x(n)
        Next n
    End If
End Function

Private Sub AddToArray(arr() As Long, x As Long)
    If (Not Not arr) <> 0 Then
        ReDim Preserve arr(0 To UBound(arr) + 1)
    Else
        ReDim Preserve arr(0 To 0)
    End If
    arr(UBound(arr)) = x
End Sub

Private Sub CopyArray(destination() As Long, source() As Long)
    Dim n As Long
    If (Not Not source) <> 0 Then
        For n = 0 To UBound(source)
                AddToArray destination, source(n)
        Next n
    End If
End Sub

La sortie (écrite dans la fenêtre Exécution) doit être:

SUM ( {3,8,4} ) = 15
SUM ( {3,5,7} ) = 15
SUM ( {8,7} ) = 15
SUM ( {5,10} ) = 15 
CodingQuant
la source
2

Voici une meilleure version avec un meilleur formatage de sortie et des fonctionnalités C ++ 11:

void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums) 
{
    int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0);
    if (currentSum > target)
        return;
    if (currentSum == target) 
    {
        std::cout << "sum([";
        for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it)
            cout << *it << ",";
        cout << *std::prev(partialNums.end());
        std::cout << "])=" << target << std::endl;
    }
    for (auto it = nums.begin(); it != nums.end(); ++it) 
    {
        std::vector<int> remaining;
        for (auto it2 = std::next(it); it2 != nums.end(); ++it2)
            remaining.push_back(*it2);

        std::vector<int> partial = partialNums;
        partial.push_back(*it);
        subset_sum_rec(remaining, target, partial);
    }
}
Andrushenko Alexander
la source
2

Version Java non récursive qui continue simplement d'ajouter des éléments et de les redistribuer parmi les valeurs possibles. 0sont ignorés et fonctionne pour des listes fixes (ce qui vous est donné est ce que vous pouvez jouer avec) ou une liste de nombres répétables.

import java.util.*;

public class TestCombinations {

    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 2, 5, 10, 20));
        LinkedHashSet<Integer> targets = new LinkedHashSet<Integer>() {{
            add(4);
            add(10);
            add(25);
        }};

        System.out.println("## each element can appear as many times as needed");
        for (Integer target: targets) {
            Combinations combinations = new Combinations(numbers, target, true);
            combinations.calculateCombinations();
            for (String solution: combinations.getCombinations()) {
                System.out.println(solution);
            }
        }

        System.out.println("## each element can appear only once");
        for (Integer target: targets) {
            Combinations combinations = new Combinations(numbers, target, false);
            combinations.calculateCombinations();
            for (String solution: combinations.getCombinations()) {
                System.out.println(solution);
            }
        }
    }

    public static class Combinations {
        private boolean allowRepetitions;
        private int[] repetitions;
        private ArrayList<Integer> numbers;
        private Integer target;
        private Integer sum;
        private boolean hasNext;
        private Set<String> combinations;

        /**
         * Constructor.
         *
         * @param numbers Numbers that can be used to calculate the sum.
         * @param target  Target value for sum.
         */
        public Combinations(ArrayList<Integer> numbers, Integer target) {
            this(numbers, target, true);
        }

        /**
         * Constructor.
         *
         * @param numbers Numbers that can be used to calculate the sum.
         * @param target  Target value for sum.
         */
        public Combinations(ArrayList<Integer> numbers, Integer target, boolean allowRepetitions) {
            this.allowRepetitions = allowRepetitions;
            if (this.allowRepetitions) {
                Set<Integer> numbersSet = new HashSet<>(numbers);
                this.numbers = new ArrayList<>(numbersSet);
            } else {
                this.numbers = numbers;
            }
            this.numbers.removeAll(Arrays.asList(0));
            Collections.sort(this.numbers);

            this.target = target;
            this.repetitions = new int[this.numbers.size()];
            this.combinations = new LinkedHashSet<>();

            this.sum = 0;
            if (this.repetitions.length > 0)
                this.hasNext = true;
            else
                this.hasNext = false;
        }

        /**
         * Calculate and return the sum of the current combination.
         *
         * @return The sum.
         */
        private Integer calculateSum() {
            this.sum = 0;
            for (int i = 0; i < repetitions.length; ++i) {
                this.sum += repetitions[i] * numbers.get(i);
            }
            return this.sum;
        }

        /**
         * Redistribute picks when only one of each number is allowed in the sum.
         */
        private void redistribute() {
            for (int i = 1; i < this.repetitions.length; ++i) {
                if (this.repetitions[i - 1] > 1) {
                    this.repetitions[i - 1] = 0;
                    this.repetitions[i] += 1;
                }
            }
            if (this.repetitions[this.repetitions.length - 1] > 1)
                this.repetitions[this.repetitions.length - 1] = 0;
        }

        /**
         * Get the sum of the next combination. When 0 is returned, there's no other combinations to check.
         *
         * @return The sum.
         */
        private Integer next() {
            if (this.hasNext && this.repetitions.length > 0) {
                this.repetitions[0] += 1;
                if (!this.allowRepetitions)
                    this.redistribute();
                this.calculateSum();

                for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
                    if (this.sum > this.target) {
                        this.repetitions[i] = 0;
                        if (i + 1 < this.repetitions.length) {
                            this.repetitions[i + 1] += 1;
                            if (!this.allowRepetitions)
                                this.redistribute();
                        }
                        this.calculateSum();
                    }
                }

                if (this.sum.compareTo(0) == 0)
                    this.hasNext = false;
            }
            return this.sum;
        }

        /**
         * Calculate all combinations whose sum equals target.
         */
        public void calculateCombinations() {
            while (this.hasNext) {
                if (this.next().compareTo(target) == 0)
                    this.combinations.add(this.toString());
            }
        }

        /**
         * Return all combinations whose sum equals target.
         *
         * @return Combinations as a set of strings.
         */
        public Set<String> getCombinations() {
            return this.combinations;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder("" + sum + ": ");
            for (int i = 0; i < repetitions.length; ++i) {
                for (int j = 0; j < repetitions[i]; ++j) {
                    stringBuilder.append(numbers.get(i) + " ");
                }
            }
            return stringBuilder.toString();
        }
    }
}

Exemple d'entrée:

numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25

Exemple de sortie:

## each element can appear as many times as needed
4: 1 1 1 1 
4: 1 1 2 
4: 2 2 
10: 1 1 1 1 1 1 1 1 1 1 
10: 1 1 1 1 1 1 1 1 2 
10: 1 1 1 1 1 1 2 2 
10: 1 1 1 1 2 2 2 
10: 1 1 2 2 2 2 
10: 2 2 2 2 2 
10: 1 1 1 1 1 5 
10: 1 1 1 2 5 
10: 1 2 2 5 
10: 5 5 
10: 10 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 
25: 1 1 1 2 2 2 2 2 2 2 2 2 2 2 
25: 1 2 2 2 2 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 5 
25: 1 1 1 1 1 1 2 2 2 2 2 2 2 5 
25: 1 1 1 1 2 2 2 2 2 2 2 2 5 
25: 1 1 2 2 2 2 2 2 2 2 2 5 
25: 2 2 2 2 2 2 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 5 5 
25: 1 1 1 1 1 1 1 1 1 2 2 2 5 5 
25: 1 1 1 1 1 1 1 2 2 2 2 5 5 
25: 1 1 1 1 1 2 2 2 2 2 5 5 
25: 1 1 1 2 2 2 2 2 2 5 5 
25: 1 2 2 2 2 2 2 2 5 5 
25: 1 1 1 1 1 1 1 1 1 1 5 5 5 
25: 1 1 1 1 1 1 1 1 2 5 5 5 
25: 1 1 1 1 1 1 2 2 5 5 5 
25: 1 1 1 1 2 2 2 5 5 5 
25: 1 1 2 2 2 2 5 5 5 
25: 2 2 2 2 2 5 5 5 
25: 1 1 1 1 1 5 5 5 5 
25: 1 1 1 2 5 5 5 5 
25: 1 2 2 5 5 5 5 
25: 5 5 5 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 10 
25: 1 1 1 1 1 1 1 1 1 2 2 2 10 
25: 1 1 1 1 1 1 1 2 2 2 2 10 
25: 1 1 1 1 1 2 2 2 2 2 10 
25: 1 1 1 2 2 2 2 2 2 10 
25: 1 2 2 2 2 2 2 2 10 
25: 1 1 1 1 1 1 1 1 1 1 5 10 
25: 1 1 1 1 1 1 1 1 2 5 10 
25: 1 1 1 1 1 1 2 2 5 10 
25: 1 1 1 1 2 2 2 5 10 
25: 1 1 2 2 2 2 5 10 
25: 2 2 2 2 2 5 10 
25: 1 1 1 1 1 5 5 10 
25: 1 1 1 2 5 5 10 
25: 1 2 2 5 5 10 
25: 5 5 5 10 
25: 1 1 1 1 1 10 10 
25: 1 1 1 2 10 10 
25: 1 2 2 10 10 
25: 5 10 10 
25: 1 1 1 1 1 20 
25: 1 1 1 2 20 
25: 1 2 2 20 
25: 5 20 
## each element can appear only once
4: 2 2 
10: 1 2 2 5 
10: 10 
25: 1 2 2 20 
25: 5 20
Bernat
la source
1

Pour trouver les combinaisons en utilisant Excel - (c'est assez facile). (Votre ordinateur ne doit pas être trop lent)

  1. Accéder à ce site
  2. Accédez à la page "Sum to Target"
  3. Téléchargez le fichier Excel "Sum to Target".

    Suivez les instructions sur la page du site Web.

J'espère que cela t'aides.

Mark van Zoest
la source
1

Conversion Swift 3 de la solution Java: (par @JeremyThompson)

protocol _IntType { }
extension Int: _IntType {}


extension Array where Element: _IntType {

    func subsets(to: Int) -> [[Element]]? {

        func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {

            var sum: Int = 0
            for x in partial {
                sum += x as! Int
            }

            if sum == target {
                solution.append(partial)
            }

            guard sum < target else {
                return
            }

            for i in stride(from: 0, to: numbers.count, by: 1) {

                var remaining = [Element]()

                for j in stride(from: i + 1, to: numbers.count, by: 1) {
                    remaining.append(numbers[j])
                }

                var partial_rec = [Element](partial)
                partial_rec.append(numbers[i])

                sum_up_recursive(remaining, target, partial_rec, &solution)
            }
        }

        var solutions = [[Element]]()
        sum_up_recursive(self, to, [Element](), &solutions)

        return solutions.count > 0 ? solutions : nil
    }

}

usage:

let numbers = [3, 9, 8, 4, 5, 7, 10]

if let solution = numbers.subsets(to: 15) {
    print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
    print("not possible")
}
RolandasR
la source
1

Cela peut également être utilisé pour imprimer toutes les réponses

public void recur(int[] a, int n, int sum, int[] ans, int ind) {
    if (n < 0 && sum != 0)
        return;
    if (n < 0 && sum == 0) {
        print(ans, ind);
        return;
    }
    if (sum >= a[n]) {
        ans[ind] = a[n];
        recur(a, n - 1, sum - a[n], ans, ind + 1);
    }
    recur(a, n - 1, sum, ans, ind);
}

public void print(int[] a, int n) {
    for (int i = 0; i < n; i++)
        System.out.print(a[i] + " ");
    System.out.println();
}

La complexité temporelle est exponentielle. Ordre de 2 ^ n

Astha Gupta
la source
1

Je faisais quelque chose de similaire pour une mission de scala. Pensé à poster ma solution ici:

 def countChange(money: Int, coins: List[Int]): Int = {
      def getCount(money: Int, remainingCoins: List[Int]): Int = {
        if(money == 0 ) 1
        else if(money < 0 || remainingCoins.isEmpty) 0
        else
          getCount(money, remainingCoins.tail) +
            getCount(money - remainingCoins.head, remainingCoins)
      }
      if(money == 0 || coins.isEmpty) 0
      else getCount(money, coins)
    }
Prabodh Mhalgi
la source
1

J'ai porté l'exemple C # sur Objective-c et je ne l'ai pas vu dans les réponses:

//Usage
NSMutableArray* numberList = [[NSMutableArray alloc] init];
NSMutableArray* partial = [[NSMutableArray alloc] init];
int target = 16;
for( int i = 1; i<target; i++ )
{ [numberList addObject:@(i)]; }
[self findSums:numberList target:target part:partial];


//*******************************************************************
// Finds combinations of numbers that add up to target recursively
//*******************************************************************
-(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial
{
    int s = 0;
    for (NSNumber* x in partial)
    { s += [x intValue]; }

    if (s == target)
    { NSLog(@"Sum[%@]", partial); }

    if (s >= target)
    { return; }

    for (int i = 0;i < [numbers count];i++ )
    {
        int n = [numbers[i] intValue];
        NSMutableArray* remaining = [[NSMutableArray alloc] init];
        for (int j = i + 1; j < [numbers count];j++)
        { [remaining addObject:@([numbers[j] intValue])]; }

        NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial];
        [partRec addObject:@(n)];
        [self findSums:remaining target:target part:partRec];
    }
}
JMan Mousey
la source
1

@ Réponse de KeithBeller avec des noms de variables légèrement modifiés et quelques commentaires.

    public static void Main(string[] args)
    {
        List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
        int targetSum = 15;
        SumUp(input, targetSum);
    }

    public static void SumUp(List<int> input, int targetSum)
    {
        SumUpRecursive(input, targetSum, new List<int>());
    }

    private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum)
    {
        // Sum up partial
        int sum = 0;
        foreach (int x in listToSum)
            sum += x;

        //Check sum matched
        if (sum == targetSum)
            Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum);

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.Count; i++)
        {
            //Build list of remaining items to iterate
            List<int> newRemaining = new List<int>();
            for (int j = i + 1; j < remaining.Count; j++)
                newRemaining.Add(remaining[j]);

            //Update partial list
            List<int> newListToSum = new List<int>(listToSum);
            int currentItem = remaining[i];
            newListToSum.Add(currentItem);
            SumUpRecursive(newRemaining, targetSum, newListToSum);
        }
    }'
strider
la source
1

Version PHP , inspirée de la version C # de Keith Beller.

La version PHP de bala ne fonctionnait pas pour moi, car je n'avais pas besoin de grouper les numéros. Je voulais une implémentation plus simple avec une valeur cible et un pool de nombres. Cette fonction supprimera également toutes les entrées en double.

/**
 * Calculates a subset sum: finds out which combinations of numbers
 * from the numbers array can be added together to come to the target
 * number.
 * 
 * Returns an indexed array with arrays of number combinations.
 * 
 * Example: 
 * 
 * <pre>
 * $matches = subset_sum(array(5,10,7,3,20), 25);
 * </pre>
 * 
 * Returns:
 * 
 * <pre>
 * Array
 * (
 *   [0] => Array
 *   (
 *       [0] => 3
 *       [1] => 5
 *       [2] => 7
 *       [3] => 10
 *   )
 *   [1] => Array
 *   (
 *       [0] => 5
 *       [1] => 20
 *   )
 * )
 * </pre>
 * 
 * @param number[] $numbers
 * @param number $target
 * @param array $part
 * @return array[number[]]
 */
function subset_sum($numbers, $target, $part=null)
{
    // we assume that an empty $part variable means this
    // is the top level call.
    $toplevel = false;
    if($part === null) {
        $toplevel = true;
        $part = array();
    }

    $s = 0;
    foreach($part as $x) 
    {
        $s = $s + $x;
    }

    // we have found a match!
    if($s == $target) 
    {
        sort($part); // ensure the numbers are always sorted
        return array(implode('|', $part));
    }

    // gone too far, break off
    if($s >= $target) 
    {
        return null;
    }

    $matches = array();
    $totalNumbers = count($numbers);

    for($i=0; $i < $totalNumbers; $i++) 
    {
        $remaining = array();
        $n = $numbers[$i];

        for($j = $i+1; $j < $totalNumbers; $j++) 
        {
            $remaining[] = $numbers[$j];
        }

        $part_rec = $part;
        $part_rec[] = $n;

        $result = subset_sum($remaining, $target, $part_rec);
        if($result) 
        {
            $matches = array_merge($matches, $result);
        }
    }

    if(!$toplevel) 
    {
        return $matches;
    }

    // this is the top level function call: we have to
    // prepare the final result value by stripping any
    // duplicate results.
    $matches = array_unique($matches);
    $result = array();
    foreach($matches as $entry) 
    {
        $result[] = explode('|', $entry);
    }

    return $result;
}
AeonOfTime
la source
1

Recommandé comme réponse:

Voici une solution utilisant des générateurs es2015 :

function* subsetSum(numbers, target, partial = [], partialSum = 0) {

  if(partialSum === target) yield partial

  if(partialSum >= target) return

  for(let i = 0; i < numbers.length; i++){
    const remaining = numbers.slice(i + 1)
        , n = numbers[i]

    yield* subsetSum(remaining, target, [...partial, n], partialSum + n)
  }

}

L'utilisation de générateurs peut en fait être très utile car elle vous permet de suspendre l'exécution du script immédiatement après avoir trouvé un sous-ensemble valide. Ceci contraste avec les solutions sans générateurs (c.-à-d. Manquant d’état) qui doivent parcourir tous les sous-ensembles denumbers

feihcsim
la source
1

Déduisez 0 en premier lieu. Le zéro est une identité pour l'addition, il est donc inutile par les lois monoïdes dans ce cas particulier. Déduisez également des nombres négatifs si vous voulez grimper jusqu'à un nombre positif. Sinon, vous auriez également besoin d'une opération de soustraction.

Donc ... l'algorithme le plus rapide que vous pouvez obtenir pour ce travail particulier est le suivant donné dans JS.

function items2T([n,...ns],t){
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var data = [3, 9, 8, 4, 5, 7, 10],
    result;

console.time("combos");
result = items2T(data, 15);
console.timeEnd("combos");
console.log(JSON.stringify(result));

Il s'agit d'un algorithme très rapide, mais si vous triez le datatableau en ordre décroissant, il sera encore plus rapide. L'utilisation .sort()est insignifiante car l'algorithme se terminera par des invocations beaucoup moins récursives.

Redu
la source
Agréable. Cela montre que vous êtes un programmeur expérimenté :)
James P.
1

Version Perl (de la réponse principale):

use strict;

sub subset_sum {
  my ($numbers, $target, $result, $sum) = @_;

  print 'sum('.join(',', @$result).") = $target\n" if $sum == $target;
  return if $sum >= $target;

  subset_sum([@$numbers[$_ + 1 .. $#$numbers]], $target, 
             [@{$result||[]}, $numbers->[$_]], $sum + $numbers->[$_])
    for (0 .. $#$numbers);
}

subset_sum([3,9,8,4,5,7,10,6], 15);

Résultat:

sum(3,8,4) = 15
sum(3,5,7) = 15
sum(9,6) = 15
sum(8,7) = 15
sum(4,5,6) = 15
sum(5,10) = 15

Version Javascript:

const subsetSum = (numbers, target, partial = [], sum = 0) => {
  if (sum < target)
    numbers.forEach((num, i) =>
      subsetSum(numbers.slice(i + 1), target, partial.concat([num]), sum + num));
  else if (sum == target)
    console.log('sum(%s) = %s', partial.join(), target);
}

subsetSum([3,9,8,4,5,7,10,6], 15);

Javascript one-liner qui retourne réellement les résultats (au lieu de l'imprimer):

const subsetSum=(n,t,p=[],s=0,r=[])=>(s<t?n.forEach((l,i)=>subsetSum(n.slice(i+1),t,[...p,l],s+l,r)):s==t?r.push(p):0,r);

console.log(subsetSum([3,9,8,4,5,7,10,6], 15));

Et mon préféré, une ligne avec rappel:

const subsetSum=(n,t,cb,p=[],s=0)=>s<t?n.forEach((l,i)=>subsetSum(n.slice(i+1),t,cb,[...p,l],s+l)):s==t?cb(p):0;

subsetSum([3,9,8,4,5,7,10,6], 15, console.log);

niry
la source
0
function solve(n){
    let DP = [];

     DP[0] = DP[1] = DP[2] = 1;
     DP[3] = 2;

    for (let i = 4; i <= n; i++) {
      DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
    }
    return DP[n]
}

console.log(solve(5))

Il s'agit d'une solution dynamique pour JS permettant de savoir de combien de façons n'importe qui peut obtenir une certaine somme. Cela peut être la bonne solution si vous pensez à la complexité du temps et de l'espace.

Dheerendra Dev
la source
0
import java.util.*;

public class Main{

     int recursionDepth = 0;
     private int[][] memo;

     public static void main(String []args){
         int[] nums = new int[] {5,2,4,3,1};
         int N = nums.length;
         Main main =  new Main();
         main.memo = new int[N+1][N+1];
         main._findCombo(0, N-1,nums, 8, 0, new LinkedList() );
         System.out.println(main.recursionDepth);
     }


       private void _findCombo(
           int from,
           int to,
           int[] nums,
           int targetSum,
           int currentSum,
           LinkedList<Integer> list){

            if(memo[from][to] != 0) {
                currentSum = currentSum + memo[from][to];
            }

            if(currentSum > targetSum) {
                return;
            }

            if(currentSum ==  targetSum) {
                System.out.println("Found - " +list);
                return;
            }

            recursionDepth++;

           for(int i= from ; i <= to; i++){
               list.add(nums[i]);
               memo[from][i] = currentSum + nums[i];
               _findCombo(i+1, to,nums, targetSum, memo[from][i], list);
                list.removeLast();
           }

     }
}
Neel Salpe
la source
0

Je n'ai pas aimé la solution Javascript. J'ai vu pourquoi j'en construisais une sur myselft en utilisant des applications partielles, des fermetures et des récursions:

Ok, je me demandais principalement si le tableau de combinaisons pouvait satisfaire la cible requise, mais avec cette approche, vous pouvez commencer à trouver le reste des combinaisons

Ici, définissez simplement la cible et passez le tableau des combinaisons.

function main() {
    const target = 10
    const getPermutationThatSumT = setTarget(target)
    const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])

    console.log( permutation );
}

la mise en œuvre actuelle, je suis venu avec

function setTarget(target) {
    let partial = [];

    return function permute(input) {
        let i, removed;
        for (i = 0; i < input.length; i++) {
            removed = input.splice(i, 1)[0];
            partial.push(removed);

            const sum = partial.reduce((a, b) => a + b)
            if (sum === target) return partial.slice()
            if (sum < target) permute(input)

            input.splice(i, 0, removed);
            partial.pop();
        }
        return null
    };
}
Luillyfe
la source