Jak poszedłbyś przetestować wszystkie możliwe kombinacje dodatków z danego zestawu N
liczb, aby sumowały się one do podanej liczby końcowej?
Krótki przykład:
- Zestaw liczb do dodania:
N = {1,5,22,15,0,...}
- Pożądany rezultat:
12345
Jak poszedłbyś przetestować wszystkie możliwe kombinacje dodatków z danego zestawu N
liczb, aby sumowały się one do podanej liczby końcowej?
Krótki przykład:
N = {1,5,22,15,0,...}
12345
Odpowiedzi:
Problem ten można rozwiązać za pomocą rekurencyjnych kombinacji wszystkich możliwych kwot odfiltrowujących te, które osiągają cel. Oto algorytm w Pythonie:
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
Tego rodzaju algorytmy są bardzo dobrze wyjaśnione w następującym wykładzie Standford's Abstract Programming - ten film jest bardzo godny polecenia, aby zrozumieć, jak rekurencja działa w celu generowania permutacji rozwiązań.
Edytować
Powyżej jako funkcja generatora, dzięki czemu jest nieco bardziej przydatna. Wymaga Python 3.3+ z powodu 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)
Oto wersja Java tego samego algorytmu:
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);
}
}
To jest dokładnie ta sama heurystyka. Moja Java jest trochę zardzewiała, ale myślę, że jest łatwa do zrozumienia.
Konwersja C # rozwiązania Java: (autor: @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);
}
}
Rozwiązanie Ruby: (autor @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)
Edycja: dyskusja złożoności
Jak wspominają inni, jest to trudny problem NP . Można go rozwiązać w czasie wykładniczym O (2 ^ n), na przykład dla n = 10 będzie 1024 możliwych rozwiązań. Jeśli cele, które próbujesz osiągnąć, znajdują się w niskim zakresie, algorytm działa. Na przykład:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000)
generuje 1024 gałęzie, ponieważ cel nigdy nie odfiltruje możliwych rozwiązań.
Z drugiej strony subset_sum([1,2,3,4,5,6,7,8,9,10],10)
generuje tylko 175 gałęzi, ponieważ cel do osiągnięcia 10
pozwala odfiltrować wiele kombinacji.
Jeśli N
i Target
są dużymi liczbami, należy przejść do przybliżonej wersji rozwiązania.
[1, 2, 0, 6, -3, 3], 3
- wyświetla tylko [1,2], [0,3], [3]
przy brakujących przypadkach, takich jak[6, -3, 3]
[1, 2, 5], 5
tylko wyjść [5]
, kiedy [1, 1, 1, 1, 1]
, [2, 2, 1]
i [2, 1, 1, 1]
są rozwiązaniami.
i+1
in remaining = numbers[i+1:]
. Wygląda na to, że ten algorytm nie zezwala na duplikaty.
[1, 1, 3]
spojrzeć na stackoverflow.com/a/34971783/3684296 (Python)
Rozwiązanie tego problemu podano milion razy w Internecie. Problem nazywa się Problem zmiany monety . Rozwiązania można znaleźć na stronie http://rosettacode.org/wiki/Count_the_coins, a jej matematyczny model na stronie http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (lub zmiana monety Google problem ).
Nawiasem mówiąc, interesujące jest rozwiązanie Scala firmy Tsagadai. Ten przykład daje 1 lub 0. Jako efekt uboczny, wypisuje na konsoli wszystkie możliwe rozwiązania. Wyświetla rozwiązanie, ale nie udaje się go w żaden sposób wykorzystać.
Aby być jak najbardziej użytecznym, kod powinien zwrócić a List[List[Int]]
, aby umożliwić uzyskanie liczby rozwiązań (długość listy list), „najlepszego” rozwiązania (najkrótsza lista) lub wszystkich możliwych rozwiązań.
Oto przykład. Jest bardzo nieefektywny, ale łatwo go zrozumieć.
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")
}
Po uruchomieniu wyświetla:
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)
sumCombinations()
Funkcja może być stosowany sam, a wynik może być dalej analizowane w celu wyświetlenia „najlepsze” rozwiązanie (najkrótsza listy) lub szereg rozwiązań (liczbie List).
Pamiętaj, że nawet w ten sposób wymagania mogą nie być w pełni spełnione. Może się zdarzyć, że kolejność każdej listy w rozwiązaniu będzie znacząca. W takim przypadku każda lista musiałaby zostać zduplikowana tyle razy, ile jest kombinacji jej elementów. Lub możemy być zainteresowani tylko różnymi kombinacjami.
Na przykład możemy rozważyć, że List(5, 10)
powinny dać dwie kombinacje: List(5, 10)
i List(10, 5)
. Na List(5, 5, 5)
to może dać trzy kombinacje czy tylko jeden, w zależności od wymagań. W przypadku liczb całkowitych trzy permutacje są równoważne, ale jeśli mamy do czynienia z monetami, jak w przypadku „problemu wymiany monet”, nie są.
W wymaganiach nie podano również, czy każdy numer (lub moneta) może być użyty tylko raz, czy wiele razy. Możemy (i powinniśmy!) Uogólnić problem na listę list występowania każdej liczby. Przekłada się to w rzeczywistości na „jakie są możliwe sposoby zarabiania pewnej ilości pieniędzy za pomocą zestawu monet (a nie zestawu wartości monet)”. Pierwotny problem to tylko szczególny przypadek tego przypadku, w którym mamy tyle wystąpień każdej monety, ile potrzeba, aby uzyskać całkowitą kwotę przy każdej wartości monety.
W Haskell :
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]
I J :
(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...
Jak możesz zauważyć, obaj zastosuj to samo podejście i podziel problem na dwie części: wygeneruj każdy element zestawu mocy i sprawdź sumę każdego elementu do celu.
Istnieją inne rozwiązania, ale jest to najprostsze.
Czy potrzebujesz pomocy z jednym z nich lub szukasz innego podejścia?
not in scope: 'subsequences'
jakieś wskazówki?
import Data.List
Wersja 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
remaining = numbers.slice();
remaining.slice(i + 1);
przeciwnym razie należy numbers.slice(i + 1);
zmienić tablicę liczb
slice
zwraca (płytką) kopię, nie modyfikuje numbers
tablicy.
Wersja C ++ tego samego algorytmu
#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;
}
Wersja C # odpowiedzi na kod @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>());
}
Myślałem, że skorzystam z odpowiedzi na to pytanie, ale nie mogłem, więc oto moja odpowiedź. Wykorzystuje zmodyfikowaną wersję odpowiedzi w Strukturze i interpretacji programów komputerowych . Myślę, że jest to lepsze rozwiązanie rekurencyjne i powinno bardziej zadowolić purystów.
Moja odpowiedź jest w Scali (i przepraszam, jeśli moja Scala jest do bani, właśnie zaczęłam się uczyć). FindSumCombinations szaleństwo jest do rodzaju i niepowtarzalny oryginalnej listy do rekursji do uniknięcia powtórzeń.
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)
}
Aby go użyć:
> findSumCombinations(12345, List(1,5,22,15,0,..))
* Prints a whole heap of lists that will sum to the target *
Thank you.. ephemient
przekonwertowałem powyższą logikę z Pythona na 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();
}
?>
Innym rozwiązaniem Pythona byłoby użycie itertools.combinations
modułu w następujący sposób:
#!/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)
Wynik: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]
Oto rozwiązanie w 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))
}
}
subset_sum(numbers = c(1:2), target = 5)
zwraca "sum(1+2+2)=5"
. Brakuje jednak kombinacji 1 + 1 + 1 + 1 + 1. W ustawianiu celów na wyższe liczby (np. 20) brakuje jeszcze większej liczby kombinacji.
subset_sum(1:2, 4)
nie powinien zwracać żadnych rozwiązań, ponieważ nie ma kombinacji 1 i 2, która dodaje do 4. To, co należy dodać do mojej funkcji, to ucieczka, jeśli i
jest większa niż długośćnumbers
Oto wersja Java, która dobrze nadaje się do małej N i bardzo dużej sumy docelowej, gdy złożoność O(t*N)
(rozwiązanie dynamiczne) jest większa niż algorytm wykładniczy. Moja wersja wykorzystuje spotkanie w środkowym ataku, wraz z niewielkim przesunięciem w celu zmniejszenia złożoności z klasycznego naiwnego O(n*2^n)
do O(2^(n/2))
.
Jeśli chcesz użyć tego dla zestawów zawierających od 32 do 64 elementów, powinieneś zmienić ten, int
który reprezentuje bieżący podzbiór w funkcji kroku, na long
chociaż wydajność wyraźnie drastycznie spadnie wraz ze wzrostem rozmiaru zestawu. Jeśli chcesz użyć tego dla zestawu z nieparzystą liczbą elementów, powinieneś dodać 0 do zestawu, aby był parzysty.
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;
}
}
Jest to podobne do problemu wymiany monet
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;
}
}
Bardzo wydajny algorytm wykorzystujący tabele napisane kilka lat temu w c ++.
Jeśli ustawisz DRUKUJ 1, wydrukuje wszystkie kombinacje (ale nie będzie to efektywna metoda).
Jest tak wydajny, że oblicza ponad 10 ^ 14 kombinacji w czasie krótszym niż 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");
}
Wersja Excel VBA poniżej. Musiałem zaimplementować to w VBA (nie moje preferencje, nie oceniaj mnie!) I wykorzystałem odpowiedzi z tej strony do tego podejścia. Przesyłam na wypadek, gdyby inni również potrzebowali wersji 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
Dane wyjściowe (zapisane w oknie natychmiastowym) powinny wynosić:
SUM ( {3,8,4} ) = 15
SUM ( {3,5,7} ) = 15
SUM ( {8,7} ) = 15
SUM ( {5,10} ) = 15
Oto lepsza wersja z lepszym formatowaniem wyjściowym i funkcjami 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);
}
}
Nierekurencyjna wersja Java, która po prostu dodaje elementy i redystrybuuje je wśród możliwych wartości. 0
są ignorowane i działają na ustalonych listach (możesz się nimi bawić) lub na liście powtarzalnych liczb.
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();
}
}
}
Przykładowe dane wejściowe:
numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25
Przykładowe dane wyjściowe:
## 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
Aby znaleźć kombinacje za pomocą programu Excel - (jest dość łatwe). (Twój komputer nie może być zbyt wolny)
Pobierz plik Excel „Sum to Target”.
Postępuj zgodnie ze wskazówkami na stronie internetowej.
mam nadzieję że to pomoże.
Szybka konwersja rozwiązania Java: (autor: @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
}
}
stosowanie:
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")
}
Można to również wykorzystać do wydrukowania wszystkich odpowiedzi
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();
}
Złożoność czasu ma charakter wykładniczy. Rząd 2 ^ n
Robiłem coś podobnego do zadania Scala. Pomysł opublikowania mojego rozwiązania tutaj:
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)
}
Przeniesiłem próbkę C # do Objective-c i nie widziałem jej w odpowiedziach:
//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];
}
}
Odpowiedź KeithBellera z nieznacznie zmienionymi nazwami zmiennych i kilkoma komentarzami.
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);
}
}'
Wersja PHP , inspirowana wersją C # Keitha Bellera.
Wersja PHP bala dla mnie nie działała, ponieważ nie musiałem grupować numerów. Chciałem prostszej implementacji z jedną wartością docelową i pulą liczb. Ta funkcja również przycina wszelkie zduplikowane wpisy.
/**
* 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;
}
Zalecane jako odpowiedź:
Oto rozwiązanie wykorzystujące generatory 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)
}
}
Korzystanie z generatorów może być bardzo przydatne, ponieważ umożliwia wstrzymanie wykonywania skryptu natychmiast po znalezieniu prawidłowego podzbioru. Jest to sprzeczne z rozwiązaniami bez generatorów (tj. Bez stanu), które muszą iterować przez każdy pojedynczy podzbiórnumbers
Po pierwsze odejmij 0. Zero jest identyfikatorem do dodania, więc w tym konkretnym przypadku jest bezużyteczne przez prawa monoidów. Odejmij także liczby ujemne, jeśli chcesz wspiąć się na liczbę dodatnią. W przeciwnym razie potrzebujesz również operacji odejmowania.
Więc ... najszybszy algorytm, jaki można uzyskać w tym konkretnym zadaniu, jest następujący w 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));
Jest to bardzo szybki algorytm, ale jeśli posortujesz data
tablicę malejącą , będzie to jeszcze szybsze. Używanie .sort()
jest nieznaczne, ponieważ algorytm zakończy się znacznie mniej rekurencyjnymi wywołaniami.
Wersja Perla (wiodąca odpowiedź):
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);
Wynik:
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
Wersja 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);
Jednoliniowy skrypt Javascript, który faktycznie zwraca wyniki (zamiast go drukować):
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));
I mój ulubiony, liniowiec z oddzwanianiem:
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);
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))
Jest to dynamiczne rozwiązanie dla JS, które informuje, w jaki sposób każdy może uzyskać określoną sumę. To może być właściwe rozwiązanie, jeśli myślisz o złożoności czasu i przestrzeni.
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();
}
}
}
Nie podobało mi się rozwiązanie JavaScript. Widziałem, dlaczego buduję jeden dla siebie, stosując częściowe stosowanie, zamykanie i rekurencję:
Ok, głównie martwiłem się, czy tablica kombinacji może spełnić docelowy wymóg, ale dzięki temu podejściu możesz zacząć znajdować resztę kombinacji
Tutaj wystarczy ustawić cel i przekazać tablicę kombinacji.
function main() {
const target = 10
const getPermutationThatSumT = setTarget(target)
const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])
console.log( permutation );
}
aktualnie wdrażane przeze mnie rozwiązanie
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
};
}