Encontrar todas as combinações possíveis de números para alcançar uma determinada soma

232

Como você testaria todas as combinações possíveis de acréscimos de um determinado conjunto Nde números para que eles somassem um determinado número final?

Um breve exemplo:

  • Conjunto de números a serem adicionados: N = {1,5,22,15,0,...}
  • Resultado desejado: 12345
James P.
fonte
@ James - Acho que seu problema precisa ser esclarecido. Quais são as regras? Você pode escolher apenas alguns números? Quais números estão no conjunto? Quais são as suas restrições?
precisa saber é o seguinte
9
O artigo da wikipedia ( en.wikipedia.org/wiki/Subset_sum_problem ) até menciona que esse problema é uma boa introdução à classe de problemas NP-completos.
user57368
1
@ jmort253: Acho que não há outras restrições além de ter um conjunto de números inteiros positivos e inferiores ao número fornecido como destino. Qualquer combinação de números pode ser usada. Não é tarefa de casa, mas o tipo de problema que você terá que resolver se se candidatar a alguns empregos. Normalmente, consigo pensar em um algoritmo quando necessário, mas não sei como visualizar algo assim. Ele precisa ser decomposto de alguma forma (recursivo?).
James P.
3
@ James, você precisa das combinações ou apenas do número de subconjuntos que somam a soma?
st0le
6
Podemos usar o mesmo elemento do conjunto original mais de uma vez? Por exemplo, se a entrada é {1,2,3,5} e a meta 10, 5 + 5 = 10 é uma solução aceitável?
Alampada 23/08/2015

Respostas:

248

Esse problema pode ser resolvido com uma combinação recursiva de todas as somas possíveis, filtrando as que atingem o alvo. Aqui está o algoritmo em 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

Esse tipo de algoritmo é muito bem explicado nos seguintes aula de programação abstrata de Standford - este vídeo é muito recomendável para entender como a recursão funciona para gerar permutações de soluções.

Editar

O acima como uma função de gerador, tornando-o um pouco mais útil. Requer Python 3.3 ou superior por causa 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)

Aqui está a versão Java do mesmo algoritmo:

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);
    }
}

É exatamente a mesma heurística. Meu Java está um pouco enferrujado, mas acho fácil de entender.

Conversão de C # da solução Java: (por @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);
    }
}

Solução Ruby: (por @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)

Editar: discussão sobre complexidade

Como outros mencionam, este é um problema difícil de NP . Pode ser resolvido no tempo exponencial O (2 ^ n); por exemplo, para n = 10, haverá 1024 soluções possíveis. Se os alvos que você está tentando alcançar estiverem em um intervalo baixo, esse algoritmo funcionará. Então, por exemplo:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) gera 1024 ramificações porque o destino nunca consegue filtrar possíveis soluções.

Por outro lado, subset_sum([1,2,3,4,5,6,7,8,9,10],10)gera apenas 175 agências, porque a meta de atingir10 chega a filtrar muitas combinações.

Se Ne Targetsão grandes números, deve-se passar para uma versão aproximada da solução.

Manuel Salvadores
fonte
1
Otimização de Java: ArrayList <Integer> parcial_rec = new ArrayList <Integer> (parcial); parcial_rec.add (n); isso faz uma cópia de parcial. e assim adiciona O (N). A melhor maneira é apenas "partial.add (n)" fazer a recursão e depois "partial.remove (partial.size -1) I reran seu código para ter certeza que funciona bem..
Christian Bongiorno
4
Esta solução não funciona para todos os casos. Considere [1, 2, 0, 6, -3, 3], 3- ele apenas gera resultados [1,2], [0,3], [3]ausentes, como[6, -3, 3]
LiraNuna 11/16
11
Ele também não funciona para todas as combinações, por exemplo [1, 2, 5], 5apenas saídas [5], quando [1, 1, 1, 1, 1], [2, 2, 1]e [2, 1, 1, 1]são soluções.
Cbrad
3
@ cbrad que é por causa de i+1in remaining = numbers[i+1:]. Parece que esse algoritmo não permite duplicatas.
Leonid Vasilev
1
@cbrad Para obter também soluções, incluindo duplicatas, [1, 1, 3]dê uma olhada em stackoverflow.com/a/34971783/3684296 (Python)
Mesa
36

A solução desse problema foi dada um milhão de vezes na Internet. O problema é chamado O problema de troca de moedas . Pode-se encontrar soluções em http://rosettacode.org/wiki/Count_the_coins e modelo matemático em http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (ou troca de moeda do Google problema ).

A propósito, a solução Scala de Tsagadai é interessante. Este exemplo produz 1 ou 0. Como efeito colateral, ele lista no console todas as soluções possíveis. Ele exibe a solução, mas falha ao torná-la utilizável de qualquer forma.

Para ser o mais útil possível, o código deve retornar um List[List[Int]] para permitir obter o número de solução (comprimento da lista de listas), a solução "melhor" (a lista mais curta) ou todas as soluções possíveis.

Aqui está um exemplo. É muito ineficiente, mas é fácil de entender.

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")
}

Quando executado, ele exibe:

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)

A sumCombinations()função pode ser usada por si só e o resultado pode ser analisado posteriormente para exibir a "melhor" solução (a lista mais curta) ou o número de soluções (o número de listas).

Observe que, mesmo assim, os requisitos podem não ser totalmente satisfeitos. Pode acontecer que a ordem de cada lista na solução seja significativa. Nesse caso, cada lista teria que ser duplicada quantas vezes houver combinação de seus elementos. Ou podemos estar interessados ​​apenas nas combinações diferentes.

Por exemplo, podemos considerar que List(5, 10)deve fornecer duas combinações: List(5, 10)e List(10, 5). Pois List(5, 5, 5)poderia dar três combinações ou apenas uma, dependendo dos requisitos. Para números inteiros, as três permutações são equivalentes, mas se estamos lidando com moedas, como no "problema de troca de moedas", elas não são.

Também não é declarado nos requisitos a questão de saber se cada número (ou moeda) pode ser usado apenas uma ou várias vezes. Poderíamos (e deveríamos!) Generalizar o problema para uma lista de listas de ocorrências de cada número. Isso se traduz na vida real em "quais são as maneiras possíveis de ganhar uma certa quantia de dinheiro com um conjunto de moedas (e não um conjunto de valores de moedas)". O problema original é apenas um caso particular deste, em que temos tantas ocorrências de cada moeda quanto necessárias para fazer o valor total com cada valor de uma única moeda.

Pierre-Yves Saumont
fonte
14
Esse problema não é exatamente o mesmo que o problema de troca de moedas. O OP está pedindo todas as combinações, não apenas o mínimo. E, presumivelmente, os números inteiros no conjunto podem ser negativos. Portanto, certas otimizações do problema de troca de moedas não são possíveis com esse problema.
ThomasMcLeod
5
e também este problema permite a repetição de itens, eu não tenho certeza OP queria isso, mas mais um problema da mochila
caub
34

Em Haskell :

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

E J :

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

Como você pode notar, ambos adotam a mesma abordagem e dividem o problema em duas partes: gere cada membro do conjunto de poderes e verifique a soma de cada membro no alvo.

Existem outras soluções, mas essa é a mais direta.

Você precisa de ajuda com um deles ou encontrar uma abordagem diferente?

efémero
fonte
3
Uau, esse é um código bastante conciso. Eu estou bem com sua resposta. Eu acho que só preciso ler um pouco sobre algoritmos em geral. Vou dar uma olhada na sintaxe dos dois idiomas quando você despertou minha curiosidade.
James P.
Acabei de instalar o Haskell para tentar isso, definitivamente não posso simplesmente colar e executar, not in scope: 'subsequences'qualquer ponteiro?
Hart CO
4
@HartCO um pouco atrasado para a festa, masimport Data.List
Jir
28

Uma versão 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
fonte
O código tem um erro na fatia, deveria ser remaining = numbers.slice(); remaining.slice(i + 1);de outra forma numbers.slice(i + 1);muda a matriz números
Emeeus
@ Emeeus, não acho que seja verdade. sliceretorna uma cópia (rasa), não modifica a numbersmatriz.
Dario Seidl
@DarioSeidl sim, a fatia retorna uma cópia, não modifica a matriz, é esse o ponto, é por isso que se você não atribuí-la a uma variável, não a altera. Nesse caso, como eu entendo, temos que passar uma versão modificada, não a original. Veja isto jsfiddle.net/che06t3w/1
Emeeus
1
@Redu ... por exemplo, uma maneira fácil de fazê-lo é que, podemos modificar ligeiramente o algoritmo e usar uma função interna: jsbin.com/lecokaw/edit?js,console
rbarilani
1
O código dado não necessariamente obter todas as combinações .. por exemplo, colocando [1,2], 3 retornará apenas 1 + 2 = 3 não 1 + 1 + 1 + 1 ou 2
JuicY_Burrito
12

Versão C ++ do mesmo algoritmo

#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
fonte
11

Versão C # da resposta de código @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
fonte
4

Pensei em usar uma resposta desta pergunta, mas não consegui, então aqui está a minha resposta. Ele está usando uma versão modificada de uma resposta em Estrutura e interpretação de programas de computador . Penso que esta é uma solução recursiva melhor e deve agradar mais aos puristas.

Minha resposta está no Scala (e desculpas se o meu Scala for péssimo, eu apenas comecei a aprender). A loucura findSumCombinations é classificar e exclusivo a lista original da recursão para evitar enganos.

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)
}

Para usá-lo:

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

Eu converti acima lógica de python para 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
fonte
4

Outra solução python seria usar o itertools.combinationsmódulo da seguinte maneira:

#!/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)

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

brainasium
fonte
não funciona, por exemplo: find_sum_in_list (range (0,8), 4). Encontrado: [(4,), (0, 4), (1, 3), (0, 1, 3)]. Mas (2, 2) também é uma opção!
Andre Araujo
@AndreAraujo: não faz sentido usar 0, mas se você usar (1,8), itertools.combinations_with_replacement funciona e também gera 2,2.
Rubénisme
@Rubenisme Sim, cara! O problema foi a substituição! Obrigado! ;-)
Andre Araujo
4

Aqui está uma solução em 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))
  }
}
Marca
fonte
Estou procurando uma solução em R, mas esta não funciona para mim. Por exemplo, subset_sum(numbers = c(1:2), target = 5)retorna "sum(1+2+2)=5". Mas a combinação 1 + 1 + 1 + 1 + 1 está ausente. Definir metas para números mais altos (por exemplo, 20) está faltando ainda mais combinações.
Frederick
O que você descreve não é o que a função pretende retornar. Veja a resposta aceita. O fato de 2 ser repetido duas vezes é um artefato de como R gera e subconta séries, comportamento não pretendido.
Mark
subset_sum(1:2, 4)deve retornar nenhuma solução porque não há nenhuma combinação de 1 e 2 que adiciona a 4. O que precisa ser adicionado a minha função é uma fuga, se ifor maior do que o comprimentonumbers
Mark
3

Aqui está uma versão Java que é adequada para N pequeno e soma de destino muito grande, quando a complexidade O(t*N)(a solução dinâmica) é maior que o algoritmo exponencial. Minha versão usa um ataque no meio, junto com um pouco de mudança para reduzir a complexidade do clássico ingênuo O(n*2^n)para o clássico.O(2^(n/2)) .

Se você quiser usar isso para conjuntos com entre 32 e 64 elementos, altere o intque representa o subconjunto atual na função step para um longembora o desempenho obviamente diminua drasticamente à medida que o tamanho do conjunto aumenta. Se você quiser usar isso para um conjunto com número ímpar de elementos, adicione um 0 ao conjunto para torná-lo numerado.

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
fonte
3

Isso é semelhante a um problema de troca de moedas

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 '
fonte
2

Algoritmo muito eficiente usando tabelas que escrevi em c ++ alguns anos atrás.

Se você definir PRINT 1, imprimirá todas as combinações (mas não usará o método eficiente).

É tão eficiente que calcula mais de 10 ^ 14 combinações em menos de 10ms.

#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
fonte
Olá! Eu preciso de um código para fazer algo assim, encontrar todas as somas possíveis de conjuntos de 6 números em uma lista de 60 números. As somas devem estar no intervalo mínimo de 180, máximo de 191. Esse código pode ser ajustado para isso? Onde executar esse código na nuvem? Eu tentei sem sucesso em Codenvy
defreturn 20/09/16
2

Versão do Excel VBA abaixo. Eu precisava implementar isso no VBA (não é minha preferência, não me julgue!) E usei as respostas nesta página para a abordagem. Estou enviando caso outras pessoas também precisem de uma versão 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

A saída (gravada na janela Imediata) deve ser:

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

Aqui está uma versão melhor com melhor formatação de saída e recursos do 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
fonte
2

Versão não recursiva Java que simplesmente continua adicionando elementos e redistribuindo-os entre os valores possíveis. 0são ignorados e funcionam para listas fixas (o que você recebe é o que pode tocar) ou uma lista de números repetíveis.

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();
        }
    }
}

Entrada de amostra:

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

Saída de amostra:

## 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
fonte
1

Para encontrar as combinações usando o Excel - (é bastante fácil). (Seu computador não deve estar muito lento)

  1. Vá para este site
  2. Vá para a página "Soma ao destino"
  3. Faça o download do arquivo excel "Soma ao destino".

    Siga as instruções na página do site.

espero que isto ajude.

Mark van Zoest
fonte
1

Conversão Swift 3 da solução Java: (por @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
    }

}

uso:

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
fonte
1

Isso pode ser usado para imprimir todas as respostas também

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();
}

A complexidade do tempo é exponencial. Ordem de 2 ^ n

Astha Gupta
fonte
1

Eu estava fazendo algo semelhante para uma tarefa de scala. Pensei em postar minha solução aqui:

 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
fonte
1

Eu enviei a amostra de C # para o Objective-c e não a vi nas respostas:

//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
fonte
1

Resposta do @ KeithBeller com nomes de variáveis ​​ligeiramente alterados e alguns comentários.

    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);
        }
    }'
andarilho
fonte
1

Versão PHP , inspirada na versão C # de Keith Beller.

A versão PHP de bala não funcionou para mim, porque eu não precisava agrupar números. Eu queria uma implementação mais simples com um valor de destino e um conjunto de números. Esta função também remove quaisquer entradas duplicadas.

/**
 * 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
fonte
1

Recomendado como resposta:

Aqui está uma solução usando os geradores 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)
  }

}

O uso de geradores pode realmente ser muito útil, pois permite interromper a execução do script imediatamente após encontrar um subconjunto válido. Isso contrasta com as soluções sem geradores (isto é, com falta de estado) que precisam percorrer todos os subconjuntos denumbers

feihcsim
fonte
1

Deduzir 0 em primeiro lugar. Zero é uma identificação para adição, portanto é inútil pelas leis monóides neste caso particular. Deduza também números negativos também se você quiser subir para um número positivo. Caso contrário, você também precisaria de operação de subtração.

Então ... o algoritmo mais rápido que você pode obter nesse trabalho específico é o seguinte, fornecido em 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));

Este é um algoritmo muito rápido, mas se você classificar a datamatriz por descida , será ainda mais rápido. O uso .sort()é insignificante, pois o algoritmo terminará com invocações muito menos recursivas.

Redu
fonte
Agradável. Ele mostra que você é um programador experiente :)
James P.
1

Versão Perl (da resposta principal):

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);

Resultado:

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

Versão 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);

Uma linha de Javascript que realmente retorna resultados (em vez de imprimi-lo):

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));

E o meu favorito, uma linha com retorno de chamada:

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
fonte
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))

Esta é uma solução dinâmica para o JS dizer quantas maneiras alguém pode obter a soma certa. Essa pode ser a solução certa se você pensar em complexidade de tempo e espaço.

Dheerendra Dev
fonte
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
fonte
0

Não gostei da solução Javascript. Vi que é por isso que construo uma para mim usando aplicação parcial, fechamentos e recursão:

Ok, eu estava preocupada principalmente se a matriz de combinações poderia atender ao objetivo do requisito, mas com isso abordado, você pode começar a encontrar o restante das combinações

Aqui, apenas defina o alvo e passe a matriz de combinações.

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

    console.log( permutation );
}

a implementação atualmente eu vim com

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
fonte