我正在解决这个问题：
子集和问题将一组
X = {x1, x2 ,…, xn}整数n和另一个整数作为输入K。问题是检查是否存在其元素总和的子X'集并找到子集（如果有）。例如，如果和那么答案是因为子集的总和为。为运行时间至少为 的子集和实现算法。XKX = {5, 3, 11, 8, 2}K = 16YESX' = {5, 11}16O(nK)
注意复杂性O(nK)。我认为动态编程可能会有所帮助。
我找到了一个指数时间算法，但它没有帮助。
有人可以帮我解决这个问题吗？
子集和是我在 Macalester 学到的第一个 NP 完全问题。这个问题被查看了 36000 多次，但我没有看到足够的答案来详细解释算法的逻辑。所以我想我会尝试这样做。
假设：
为了简单起见，我首先假设输入集X只包含正整数并且k是正数。但是，我们可以调整算法以处理负整数以及 ifk为负数的情况。
逻辑：
该算法或任何 DP 问题的关键是分解问题并简单地从基本情况开始。然后我们可以使用我们知道的一些知识在基本案例的基础上进行构建：
X是空的，那么我们就无法求和 的任何值k。X包含k那么它有一个子集总和k。x1一个子集是Xsum to k1then的子集，那么它的子集就是Xsum 。k1x1X = {x1, x1, x3, ......., xn, xn+1}。我们知道它有一个子集和到k1如果x1 = {x1, x1, x3, ......., xn}有一个子集和到k - k1。举例说明 1,2,3,4：
一个集合X = {4}的子集总和为 4，因为 4 它本身就是集合的一部分
假设您有一个 setx1 = {1,3,5}是 set 的子集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。动态构建矩阵
Cool！现在让我们利用上述四个逻辑，从基本案例开始构建。我们将建立一个矩阵m。我们定义：
矩阵m有i+1行和k + 1列。
矩阵的每个单元格都有值trueor false。
m[i][s] 返回 true 或 false 以指示此问题的答案：“使用i数组中的第一项，我们可以找到一个子集总和s吗？”m[i][s]返回true是和false否
（注意维基百科的答案或大多数人构建了一个函数 m(i,s) 但我认为矩阵是理解动态编程的一种简单方法。当我们在集合或数组中只有正数时它工作得很好。但是函数路由更好，因为您不必处理超出范围的索引，匹配数组的索引并求和到矩阵......）
让我们使用示例构建矩阵：
X = {1,3,5,2,8}
k = 9
我们将逐行构建矩阵。我们最终想知道单元 m[n][k] 包含trueor 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 来帮助我们填充矩阵。
m[i][s] = (X[i-1] == s)rememebr m[i] 指的是 X 中的第 i 个项目，即 X[i-1]m[i][s] = (m[i-1][s])这是在查看上面的单元格直接。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)。看起来它应该是多项式的，但事实并非如此！它实际上是伪多项式。在这里阅读
同样，这仅在输入仅包含正数时才有效。您可以轻松调整它以使用负数。矩阵仍然有 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 = [];
//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)));由于看起来您的所有数字都是正数，因此您可以使用动态编程来解决此问题：
Start 将是一个大小为 K+1 的布尔数组possible，第一个值为 true，其余为 false。第 i 个值将表示是否可以实现 i 的子集总和。对于集合中的每个数字 n，循环遍历possible数组，如果第 i 个值为真，则也将第 i+n 个值设置为真。
最后，如果in中的第k个值为possible真，那么就可以形成k的子集和。问题在 O(NK) 时间内解决。
维基百科关于子集和问题的页面详细解释了该算法应用于不保证为正的整数集。
我建议阅读Wiki的算法。该算法存在于那里，请参阅解决方案的伪多项式时间动态规划解决方案O(P*n)，该解决方案不是多项式时间，是 (p,n) 中的多项式，但它不是 n+log P（输入大小）中的多项式，因为P可以像 2^n 这样非常大，解 P*n = (2^n)*n 通常不是多项式时间解，但是当 p 以 n 的某个多项式函数为界时是多项式时间算法。
这个问题是NPC，但有Pseudo polynomial time算法，属于weakly NP-Complete问题，也有Strongly NP-Complete问题，也就是说，除非P=NP，否则你找不到任何pseudo polynomial time算法，这个问题不在这个问题范围内，所以不知何故很容易。
我说的尽可能简单，但这并不是强 NP 完全或弱 NP 完全问题的确切定义。
有关详细信息，请参阅Garey 和 Johnson第 4 章。
看来我迟到了，这是我的两分钱。我们将创建一个boolean[] solution[n+1][k+1]这样solution[i][j]的例子，true如果使用第一i项（索引0到i-1）我们可以j从集合中得到总和；否则false。我们solution[k][n]最终会回来：
我们可以推断出以下几点：
基于以上几点，我们可以很容易地编写如下算法。
public class SubSetSum {
boolean[][] solution;
int[] input;
int k;
public SubSetSum(int[] input, int targetSum) {
this.input = input;
this.k = targetSum;
this.solution = new boolean[input.length+1][k+1];
}
public boolean subsetSum() {
int n = input.length;
for (int i = 0; i <= n; i++) { //case 1
solution[i][0] = true;
}
for (int j = 0; j <= k; j++) { // case 2
solution[0][j] = false;
}
for (int i = 1; i <= n; i++) { // n times
for (int j = 1; j <= k; j++) { // k times and time complexity O(n*k)
if(solution[i-1][j]) {
solution[i][j] = solution[i-1][j]; // case 3
continue;
}
if(j >= input[i-1]) { // case 4
solution[i][j] = solution[i-1][j-input[i-1]];
}
}
}
return solution[n][k];
}
}
在一般情况下，没有已知的子集总和算法运行时间小于 O(2^(n/2))。
void subsetSum (int arr[], int size, int target) {
int i, j ;
int **table ;
table = (int **) malloc (sizeof(int*) * (size+1)) ;
for ( i = 0 ; i <= size ; i ++ ) {
table[i] = (int *) malloc (sizeof(int) * (target+1)) ;
table[i][0] = 1 ;
}
for ( j = 1 ; j <= target ; j ++ )
table[0][j] = 0 ;
for ( i = 1 ; i <= size ; i ++ ) {
for ( j = 1 ; j <= target ; j ++ )
table[i][j] = table[i-1][j] || (arr[i-1] <= j && table[i-1][j-arr[i-1]] ) ;
}
if ( table[size][target] == 1 )
printf ( "\ntarget sum found\n" ) ;
else printf ( "\nTarget sum do not found!\n" ) ;
free (table) ;
}
令 M 为所有元素的总和。注意 K<=M
let m be a Boolean array [0...M]
set all elements of m to be False
m[0]=1
for all numbers in the set let a[i] be the ith number
for j = M to a[i]
m[j] = m[j] | m[j-a[i]];
然后简单地测试 m[k]
boolean hasSubset(int arr[],int remSum,int lastElem){
if(remSum==0) return true;
else if(remSum!=0 && lastElem<0) return false;
if(arr[lastElem]>remSum) return hasSubset(arr, remSum, lastElem-1);
else return (hasSubset(arr, remSum, lastElem-1) ||hasSubset(arr, remSum-arr[lastElem], lastElem-1));
}
考虑第 i 个元素。它要么会为子集总和做出贡献，要么不会。如果它对总和有贡献，则“总和的值”会减少等于第 i 个元素的值。如果它没有贡献，那么我们需要在剩余元素中搜索“sum的值”。
上面的答案都很好，但并没有真正给出最广泛的概述这样的事情如何适用于正数和负数。
给定一组有序整数，定义两个变量 X 和 Y 使得
X = 负元素的总和
Y = 正元素的总和
并通过按此顺序应用这些规则来对您的初始集进行操作，就像您通过二叉树递归一样
上面的答案更加详细和准确，但是对于如何绘制二叉树有一个非常广泛的看法。这个长度对运行时有什么建议？
function subsetsum(a, n) {
var r = [];
for (var i = parseInt(a.map(function() { return 1 }).join(''), 2); i; i--) {
var b = i.toString(2).split('').reverse().map(function(v, i) {
return Number(v) * a[i]
}).filter(Boolean);
if (eval(b.join('+')) == n) r.push(b);
}
return r;
}
var a = [5, 3, 11, 8, 2];
var n = 16;
console.log(subsetsum(a, n)); // -> [[3, 11, 2], [5, 3, 8], [5, 11]]
蛮力 - 忘记排序，尝试每个组合，并且 eval 解析器击败 Array.reduce（它也适用于负数）。
具有 n^2 时间复杂度的递归解决方案
public void solveSubsetSum(){
int set[] = {2,6,6,4,5};
int sum = 9;
int n = set.length;
// check for each element if it is a part of subset whose sum is equal to given sum
for (int i=0; i<n;i++){
if (isSubsetSum(set, sum, i, n)){
Log.d("isSubset:", "true") ;
break;
}
else{
Log.d("isSubset:", "false") ;
}
k=0; // to print time complexity pattern
}
}
private boolean isSubsetSum(int[] set, int sum, int i, int n) {
for (int l=0;l<k; l++){
System.out.print("*");
// to print no of time is subset call for each element
}
k++;
System.out.println();
if (sum == 0){
return true;
}
if (i>=n){
return false;
}
if (set[i] <= sum){
// current element is less than required sum then we have to check if rest of the elements make a subset such that its sum is equal to the left sum(sum-current element)
return isSubsetSum(set, sum-set[i], ++i, n);
}
else { //if current element is greater than required sum
return isSubsetSum(set, sum, ++i, n);
}
}
最坏情况复杂度：O(n^2)
最佳情况：O(n) 即；如果第一个元素构成一个子集，其总和等于给定总和。
如果我在这里计算时间复杂度有误，请纠正我。
具有一维数组的 DP 解决方案（DP 数组处理顺序在这里很重要）。
bool subsetsum_dp(vector<int>& v, int sum)
{
int n = v.size();
const int MAX_ELEMENT = 100;
const int MAX_ELEMENT_VALUE = 1000;
static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--)
{
if (j - v[i] < 0) continue;
if (dp[j - v[i]]) dp[j] = 1;
}
}
return dp[sum] ? true : false;
}