我正在研究这个问题：
子集和问题将
X = {x1, x2 ,…, xn}整数的n和另一个整数K作为输入。问题是检查是否存在X'的子集X，其元素总和为K并且如果有则找到子集。例如，如果X = {5, 3, 11, 8, 2}和K = 16那么答案是YES，因为X' = {5, 11}子集具有16的总和。实现Subset Sum的算法，其运行时间至少为O(nK)。
注意复杂性O(nK)。我认为动态编程可能有所帮助。
我找到了一个指数时间算法，但它没有帮助。
有人可以帮我解决这个问题吗？
这个问题被观看了36000多次，但我没有看到足够的答案用逻辑详细解释算法。所以我想我会尝试这样做。
假设：
为了简单起见，我首先假设输入集X只包含正整数而k是正数。但是，如果k为负，我们可以调整算法来处理负整数和情况。
逻辑：
这个算法或者任何DP问题的关键在于解决问题并从基本情况开始。然后我们可以使用我们知道的一些知识在基础案例的基础上构建：
X为空，那么我们就无法求和k的任何值。X包含k，那么它有一个k的子集和。x1的子集X的一个子集与k1相加，那么X将有一个与k1相加的子集，即x1。X = {x1, x1, x3, ......., xn, xn+1}。我们知道如果k1有x1 = {x1, x1, x3, ......., xn}的子集和它有k - 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+1行和k + 1列。true或false。i项目我们可以找到s的子集总和吗？”m[i][s]returns true为yes和false为no（注意维基百科的答案或大多数人构建函数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来帮助我们填充矩阵。
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）。它似乎应该是多项式但它不是！它实际上是伪多项式。阅读它here
同样，这仅在输入仅包含正数时有效。您可以轻松调整它以使用负数。矩阵仍然有n + 1行但B - A + 1列。其中B是上限，A是下限（+1包括零）。矩阵仍然是你必须用下限抵消s。
从头到尾很难解释文本上的DP问题。但我希望这可以帮助那些试图理解这个问题的人。
上面的答案都很棒但是并没有真正给出最广泛的概述，这样的东西如何对正数和负数都起作用。
给定一组有序的整数，定义两个变量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）即;如果第一个元素构成一个其总和等于给定总和的子集。
如果我在这里计算时间复杂度是错误的，请纠正我。
由于看起来你的所有数字都是正数，你可以使用动态编程来解决这个问题：
Start将是一个大小为K + 1的布尔数组possible，第一个值为true，其余为false。第i个值将表示是否可以实现i的子集和。对于集合中的每个数字n，循环遍历possible数组，如果第i个值为真，则将第i + n值设置为true。
最后，如果possible中的第k个值为真，那么您可以形成k的子集和。 O（NK）时间问题解决了。
Wikipedia's page on the subset sum problem详细解释了该算法应用于不保证为正的整数集。
我建议阅读Wiki的算法。该算法存在，参见O(P*n)解的伪多项式时间动态规划解，解不是多项式时间，是（p，n）中的多项式，但它不是n + log P（输入大小）中的多项式，因为P可以非常大，如2 ^ n，解P * n =（2 ^ n）* n一般不是多项式时间解，但当p受某个多项式函数有界时，n是多项式时间算法。
这个问题是NPC，但是有一个Pseudo polynomial timeal算法，它属于weakly NP-Complete问题，还有Strongly NP-Complete问题，这意味着，你找不到任何pseudo polynomial time算法，除非P = NP，这个问题不在此一系列的问题，所以很容易。
我说这个尽可能简单，但它不是强NP完全或弱NP完全问题的确切定义。
有关详细信息，请参阅Garey and Johnson第4章。
在一般情况下，没有用于小于O（2 ^（n / 2））的子集和的已知算法。
我似乎迟到了，这是我的两分钱。如果使用第一个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];
}
}
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) ;
}
具有一维阵列的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;
}
设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个元素的值。如果它没有贡献，那么我们需要在剩余元素中搜索“和值”。