子集和问题是我在麦卡莱斯特学到的第一个NP完全问题。这个问题已经被查看了36000多次，但我没有看到一个足够详细解释算法逻辑的答案。因此，我想尝试做到这一点。
假设：
为了简单起见，我首先假设输入集合X仅包含正整数，k为正数。然而，我们可以调整算法以处理负整数和k为负数的情况。
逻辑：
这个算法或者说任何DP问题的关键是将问题分解并从基本情况开始简单地开始。然后，我们可以使用我们所知道的一些知识来构建基本情况：
- 我们知道如果集合
X为空，则无法将任何值的k相加。
- 如果集合
X包含k，则它有一个子集相加为k。
- 我们知道如果集合
x1的子集之一是X的子集且和为k1，则X将有一个子集和为k1，即x1。
- 我们有一个集合
X = {x1, x1, x3, ......., xn, xn+1}。如果x1 = {x1, x1, x3, ......., xn}中有一个子集的和为k-k1，则我们知道它有一个子集和为k1。
示例以说明1,2,3,4：
- 如果你有一个空集 {}，那么你就没有子集，因此你也没有任何子集和。
一个集合 X = {4} 有一个子集和为 4，因为 4 本身就是该集合的一部分
假设你有一个集合 x1 = {1,3,5} 是集合 X = {1,3,5,2,8} 的子集。如果 x1 有一个子集和为 k1 = 8，那么这意味着 X 也有一个子集和为 8，因为 x1 是 X 的子集
- 假设你有一个集合
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,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;
}
int n = a.length;
boolean[][] m = new boolean[n + 1][k + 1];
for(int s = 0; s <= k; s++){
m[0][s] = false;
}
for(int i = 1; i <= n; i++){
for(int s = 0; s <= k; s++){
if(s - a[i-1] >= 0){
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(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));
}
}
构建矩阵的复杂度为O((n+1)(k+1))，即O(nk)。看起来应该是多项式的，但实际上它是伪多项式的。在
这里了解更多信息。
再次说明，这仅适用于输入只包含正数的情况。您可以轻松地将其调整为使用负数的情况。矩阵仍将具有n+1行，但是
B-A+1列。其中
B是上限，
A是下限（+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 = [];
for (let i = 0; i <= y; i++) {
d[i] = [];
d[i][0] = true;
}
for (let j = 1; j <= y; j++) {
for (let i = 1; i <= x; i++) {
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;
}
}
}
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]) {
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)));
