Поиск всех возможных комбинаций чисел для достижения заданной суммы
Как бы вы проверили все возможные комбинации дополнений из заданного набора чисел, чтобы они складывались до заданного конечного числа?
пример:
- набор чисел для добавления: {1,5,22,15,0,...}
- желаемый результат: 12345
24 ответа:
эта проблема может быть решена с помощью рекурсивных комбинаций всех возможных сумм, отфильтровывая те, которые достигают цели. Вот алгоритм в 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этот тип алгоритмов очень хорошо объясняется в следующем лекция Стэндфорда по абстрактному программированию - это видео очень рекомендуется, чтобы понять, как рекурсия работает для генерации перестановок решений.
Edit
выше как функцию генератора, что делает его немного более полезным. Требуется Python 3.3+ из-за
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)вот Java-версия того же алгоритма:
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); } }это точно такая же эвристика. Мой Java немного ржавый, но я думаю, что это легко понять.
C# преобразование Java-решения:(by @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); } }Ruby решение:(by @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)редактировать: обсуждение сложности
как говорят, это NP-трудная задача. Он может быть решен в экспоненциальном времени O (2^n), например, для n=10 будет 1024 возможных решения. Если цели вы пытаетесь достичь в низком диапазоне, то этот алгоритм работает. Так, например:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000)генерирует 1024 ветви, потому что цель никогда не получает отфильтровать возможно решения.С другой стороны
subset_sum([1,2,3,4,5,6,7,8,9,10],10)генерирует только 175 ветвей, потому что цель для достижения10получает, чтобы отфильтровать много комбинаций.если
NиTargetявляются большими числами, которые следует переместить в приблизительную версию решения.
решение этой проблемы было дано в миллион раз в Интернете. Проблема называется проблема изменения монет. Можно найти решения в http://rosettacode.org/wiki/Count_the_coins и математическая модель его при http://jaqm.ro/issues/volume-5, выпуск-2 / pdfs / patterson_harmel. pdf (или Google проблема изменения монеты).
кстати, решение Scala от Tsagadai, интересно. Этот пример производит 1 или 0. В качестве побочного эффекта он перечисляет на консоли все возможные решения. Он отображает решение, но не делает его пригодным для использования в любом случае.
чтобы быть максимально полезным, код должен возвращать a
List[List[Int]]чтобы получить количество решений (длина списка списков), "лучшее" решение (самый короткий список) или все возможные решения.вот пример. Это очень неэффективно, но легко сделать понимать.
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") }при запуске он отображает:
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)The
sumCombinations()функция может использоваться сама по себе, и результат может быть дополнительно проанализирован, чтобы отобразить "лучшее" решение (самый короткий список) или количество решений (количество списков).обратите внимание, что даже так, требования не могут быть полностью удовлетворены. Может случиться так, что порядок каждого списка в решении будет значительным. В таком случае каждый список придется дублировать столько раз, сколько существует сочетание его элементов. Или нас могут интересовать только различные комбинации.
например, мы могли бы рассмотреть, что
List(5, 10)должны дать две комбинации:List(5, 10)иList(10, 5). ИбоList(5, 5, 5)он может дать три комбинации или только одну, в зависимости от требований. Для целых чисел эти три перестановки эквивалентны, но если мы имеем дело с монетами, как в "проблеме изменения монет", они не являются.тоже не в требованиях прописан вопрос о том, может ли каждый номер (или монета) использоваться только один раз или много раз. Мы могли бы (и должны!) обобщите задачу на список списков вхождений каждого числа. Это переводится в реальной жизни в "каковы возможные способы заработать определенную сумму денег с помощью набора монет (а не набора значений монет)". Исходная проблема - это просто частный случай этого, где у нас есть столько вхождений каждой монеты, сколько необходимо для получения общей суммы сумма с каждым значением одной монеты.
версия 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
C# версия кода @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>()); }
C++ версия того же алгоритма
#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; }
Я думал, что буду использовать ответ на этот вопрос, но я не мог, так что вот мой ответ. Он использует модифицированную версию ответа в структура и интерпретация компьютерных программ. Я думаю, что это лучшее рекурсивное решение и должно больше радовать пуристов.
мой ответ находится в Scala (и извинения, если мой Scala отстой, я только начал его изучать). Элемент findSumCombinations сумасшествие заключается в сортировке и уникальности исходного списка для рекурсия для предотвращения обмана.
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) }использовать:
> findSumCombinations(12345, List(1,5,22,15,0,..)) * Prints a whole heap of lists that will sum to the target *
Thank you.. ephemientя преобразовал выше логику из python в 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(); } ?>
другое решение python будет использовать
itertools.combinationsмодуль следующим образом:#!/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)выход:
[(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]
чтобы найти комбинации с помощью excel - (его довольно легко). (Компьютер не должен быть слишком медленным)
- заходим на этот сайт
- перейдите на страницу "Sum to Target"
загрузите файл excel "Sum to Target".
следуйте инструкциям на странице сайта.
надеюсь, что это помогает.
вот версия Java, которая хорошо подходит для небольших N и очень большой целевой суммы, когда сложность
O(t*N)(динамическое решение) больше, чем экспоненциальный алгоритм. Моя версия использует встречу в средней атаке, а также немного смещается, чтобы уменьшить сложность от классического наивногоO(n*2^n)доO(2^(n/2)).если вы хотите использовать это для наборов с 32 и 64 элементами, вы должны изменить
int, который представляет текущее подмножество в шаг функции кlongхотя производительность, очевидно, резко снизится по мере увеличения размера набора. Если вы хотите использовать это для набора с нечетным числом элементов, вы должны добавить 0 к набору, чтобы сделать его четным.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; } }
это похоже на проблему изменения монеты
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; } }
очень эффективный алгоритм с использованием таблиц, которые я написал в c++ пару лет назад.
Если вы установите PRINT 1 он будет печатать все комбинации (но это не будет использовать эффективный метод).
его настолько эффективно, что он вычисляет более 10^14 комбинаций менее чем за 10 мс.
#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"); }
Java нерекурсивная версия, которая просто продолжает добавлять элементы и перераспределять их среди возможных значений.
0' s игнорируются и работает для фиксированных списков (то, что вам дано, - это то, с чем вы можете играть) или список повторяемых чисел.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(); } } }пример ввода:
numbers: 0, 1, 2, 2, 5, 10, 20 targets: 4, 10, 25пример вывода:
## 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
Swift 3 преобразование решения Java: (by @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 } }использование:
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") }
Это может быть использовано для печати всех ответов, а также
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(); }сложность экспоненциальная. Порядка 2^n
Я делал что-то подобное для задания scala. Мысль о публикации моего решения здесь:
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) }
версия Excel VBA ниже. Мне нужно было реализовать это в VBA (не мое предпочтение, не судите меня!), и использовал ответы на этой странице для подхода. Я загружаю в случае, если другие также нуждаются в версии 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вывод (записывается в непосредственное окно) должен быть:
SUM ( {3,8,4} ) = 15 SUM ( {3,5,7} ) = 15 SUM ( {8,7} ) = 15 SUM ( {5,10} ) = 15
вот лучшая версия с лучшим форматированием вывода и 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); } }
вот решение в 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)) } }
я портировал образец C# на Objective-c и не видел его в ответах:
//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]; } }
ответ @ KeithBeller с немного измененными именами переменных и некоторыми комментариями.
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); } }'
PHP версии, как вдохновлено версией C# кита Беллера.
PHP-версия bala не работала для меня, потому что мне не нужно было группировать числа. Я хотел более простую реализацию с одним целевым значением и пулом чисел. Эта функция также будет обрезать любые повторяющиеся записи.
/** * 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; }
рекомендовано в качестве ответа:
вот решение с помощью 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) } }использование генераторов на самом деле может быть очень полезно, потому что это позволяет приостановить выполнение скрипта сразу же после нахождения допустимого подмножества. Это в отличие от решений без генераторов (т. е. отсутствие состояния), которые должны перебирать каждое подмножество
numbers