下面是一个Java版本，它非常适合小N和非常大的目标和，当复杂度O(t*N)(动态解)大于指数算法时。我的版本在中间攻击中使用了一个meet，并进行了一些调整，以降低复杂度，从经典的naive O(n*2^n)降低到O(2^(n/2))。

如果你想在32到64个元素之间的集合中使用这种方法，你应该将表示step函数中当前子集的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;
    }
}

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

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

Java非递归版本，简单地添加元素并在可能的值之间重新分配它们。0被忽略，适用于固定的列表(给定的是您可以使用的)或可重复的数字列表。

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

首先推导0。0是加法的一个恒等式所以在这个特殊情况下，它在单类定律下是没有用的。如果你想向上爬到一个正数，也可以推导出负数。否则还需要做减法运算。

所以…在这个特定的作业中，你能得到的最快算法如下所示。

函数items2T ([n,……ns), t) { Var c = ~~(t/n); 返回ns。长度呢?数组(c + 1) .fill () .reduce((r，_，i) => r.concat(items2T(ns, t-n*i)。map(s => Array(i).fill(n).concat(s)))，[]) : t % n ?［］ :[数组(c) .fill (n)); }; Var数据= [3,9,8,4,5,7,10]， 结果; console.time(“组合”); result = items2T(data, 15); console.timeEnd(“组合”); console.log (JSON.stringify(结果));

这是一个非常快的算法，但如果你对数据数组进行降序排序，它会更快。使用.sort()是无关紧要的，因为算法最终会减少递归调用。

我在做类似的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)
    }