子集总和是我在Macalester学习的第一个NP完全问题。这个问题被浏览了36000多次，但我没有看到足够的答案来用逻辑详细解释算法。所以我想我尝试这样做。

假设：

为了简单起见，我首先假设输入集X仅包含正整数并且k为正。但是，我们可以调整算法以处理负整数，如果if k为负的话。

逻辑：

该算法或实际上 任何DP问题的关键是分解问题并从基本情况开始。 那么我们可以使用一些已知的知识在基本案例的基础上进行构建：

1. 我们知道，如果集合X为空，则无法求和为的任何值k。
2. 如果集合X包含，k则其子集总和为k。
3. 我们知道，如果集合的子集x1是谁的子集X总和k1，然后X将有一个子集总和k1即x1。
4. 我们有一套X = {x1, x1, x3, ......., xn, xn+1}。我们知道它有一个子集之和k1，如果x1 = {x1, x1, x3, ......., xn}有一个子集总和k - k1。

举例说明1,2,3,4：

1. 这很容易。如果您有一个空集{}。您不能有一个子集，因此您不能有任何子集总和。

2. 集合X = {4}的子集总和为4，因为4本身是集合的一部分

3. 说您有一个集合x1 = {1,3,5}，该集合是集合的子集X = {1,3,5,2,8}。如果x1有一个子集总和，k1 = 8则意味着X也有一个子集总和为8​​，因为x1是X

4. 说您有一个集合X = {1,3,5,2,19}，我们想知道它的子集总和是否为20。它确实有一种方法可以知道x1 = {1,3,5,2}该子集的总和为（20-19）=1。因为x1的子集总和为1，则当我们将19加到集合x1上时，我们可以采用新的数字1 + 19 = 20来创建所需的总和20。

动态构建矩阵 酷！现在让我们利用以上四种逻辑，从基本情况开始构建。我们将建立一个矩阵m。我们定义：

• 矩阵m有i+1行和k + 1列。

• 矩阵的每个单元格都有true或值false。

• m [i] [s]返回true或false表示该问题的答案：“使用i数组中的第一个项目，我们可以找到要和的子集总和s吗？” m[i][s]返回trueyes和falseno

（请注意维基百科的答案，或者大多数人都建立了函数m（i，s），但是我认为矩阵是理解动态编程的一种简便方法。当我们在集合或数组中只有正数时，它很好用。函数路由更好，因为您不必处理索引超出范围，匹配数组的索引并求和到矩阵....）

让我们使用示例构建矩阵：

X = {1,3,5,2,8}
k = 9

我们将逐行构建矩阵。我们最终想知道单元格m [n] [k]包含true或false。

第一行： 逻辑1.告诉我们矩阵的第一行都应该是false。

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1|
2|
3|
4|
5|

第二行及以上： 然后对于第二行或以上，我们可以使用逻辑2,3,4帮助我们填充矩阵。

• 逻辑2告诉我们，m[i][s] = (X[i-1] == s)记忆变量m [i]指的是X中的第i个项，即X [i-1]
• 逻辑3告诉我们m[i][s] = (m[i-1][s])这是在看上面的单元格透明度。
• 逻辑4告诉我们，m[i][s] = (m[i-1][s - X[i-1]])这是在看X [i-1]单元上方和左侧的行。

如果其中任何一个是true那么m[i][s]的true，否则false。所以我们可以将2,3,4改写成m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])

使用以上逻辑来填充矩阵m。在我们的示例中，它看起来像这样。

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F 
3| F T F T T T T F T T
4| F T T T T T T T T T 
5| F T T T T T T T T T

现在使用矩阵来回答您的问题：

看看m[5][9]哪个是原始问题。使用前5个项目（即所有项目），我们可以找到9（k）的子集总和吗？答案由该单元格指示true

这是代码：

import java.util.*;

public class SubSetSum {

    public static boolean subSetSum(int[] a, int k){

        if(a == null){
            return false;
        }

        //n items in the list
        int n = a.length; 
        //create matrix m
        boolean[][] m = new boolean[n + 1][k + 1]; //n + 1 to include 0, k + 1 to include 0

        //set first row of matrix to false. This also prevent array index out of bounds: -1
        for(int s = 0; s <= k; s++){
            m[0][s] = false;
        }

        //populate matrix m
        for(int i = 1; i <= n; i++){
            for(int s = 0; s <= k; s++){    
                if(s - a[i-1] >= 0){ //when it goes left we don't want it to go out of bounds. (logic 4)
                    m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]); 
                } else {
                    m[i][s] = (m[i-1][s] || a[i-1] == s);
                }

            }
        }

        //print matrix
        print(m);

        return m[n][k];

    }

    private static void print(boolean[][] m){
        for(int i = 0; i < m.length; i++){
            for(int j = 0; j < m[i].length; j++){
                if(m[i][j]){
                    System.out.print("T");
                } else {
                    System.out.print("F");
                }           
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args){
        int[] array = {1,3,5,2,8};
        int k = 9;

        System.out.println(subSetSum(array,k));

    }
}

要构建矩阵，m需要O（（n + 1）（k +
1）），即O（nk）。似乎应该是多项式，但不是！它实际上是伪多项式。在这里阅读

同样，这仅在输入仅包含正数的情况下有效。您可以轻松调整它以使用负数tho。矩阵仍将具有n + 1行但具有B - A + 1列。其中B上限A是上限，下限是+1（包括零在内的+1）。矩阵仍然是您将必须s用下限进行偏移。

从头到尾用文本来解释DP问题是非常困难的。但我希望这对那些试图了解此问题的人有所帮助。

请注意，在以上示例中，DP表的行已排序。事实并非如此。

这是针对问题情况的DP表，即给定一组{5，3，11，8，2}。为简洁起见，我省略了错误的值。

┌─────────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ (index) │  0   │  2   │  3   │  5   │  7   │  8   │  10  │  11  │  13  │  14  │  15  │  16  │
├─────────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│    0    │ true │      │      │      │      │      │      │      │      │      │      │      │
│    5    │ true │      │      │ true │      │      │      │      │      │      │      │      │
│    3    │ true │      │ true │ true │      │ true │      │      │      │      │      │      │
│    11   │ true │      │ true │ true │      │ true │      │ true │      │ true │      │ true │
│    8    │ true │      │ true │ true │      │ true │      │ true │ true │ true │      │ true │
│    2    │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │
└─────────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

以下是JavaScript的实现，该实现将输出目标集{5，11}：

var subSetSum = function(input, sum) {



    let y = input.length;

    let x = sum;



    if(input.length === 0) return 0;



    let d = [];



    //fill the rows

    for (let i = 0; i <= y; i++) {

      d[i] = [];

      d[i][0] = true;

    }



    for (let j = 1; j <= y; j++) { //j row

      for (let i = 1; i <= x; i++) { //i column

      let num = input[j-1];

        if(num === i) {

          d[j][i] = true;

        } else if(d[j-1][i]) {

          d[j][i] = true;

        } else if (d[j-1][i-num]) {

          d[j][i] = true;

        }

      }

    }



    //console.table(d); //uncomment to see the table

    if(!d[y][x]) return null;



    let searchedSet = [];

    for(let j=input.length, i=sum; j>0 && i != 0; j--) {

      if(input[j-1] !== i) {

        while(d[j-1][i]) { // go up

          j--;

        }

      }

      searchedSet.push(input[j-1]);

      i = i-input[j-1];

    }



    return searchedSet;

};



console.log('searched set:'+ JSON.stringify(subSetSum([5, 3, 11, 8, 2], 16)));