计算子集和为k的子集数量

Question

给定一个数组，我们需要找出具有恰好等于给定整数k的和的子集数量。 请提供此问题的最优算法。这里不需要实际的子集只需要计数即可。

数组由负数和非负数整数组成。

例子： 数组 -> {1,4,-1,10,5} 绝对值和->9 答案应该是{4,5}和{-1,10}，共2个子集。

- Abhra Dasgupta

---

你尝试过任何事情吗？有什么第一反应吗？ - dhrumeel

你的数组中有负数吗？整数还是浮点数？有尝试过吗？ - hivert

存在一个多项式解决方案来处理“子数组”。你的“子集”是否意味着“子数组”？请给出一个例子。 - Aseem Goyal

Answer 1

这是子集和问题的变体，它被认为是NP难问题 - 因此目前没有已知的多项式解决方案。(事实上，子集和问题指出即使给定总和，找到一个子集的总和也很困难)。

解决它的可能方法是暴力枚举（检查所有可能的子集），或者如果集合包含相对较小的整数，则可以使用伪多项式动态规划技术：

f(i,0) = 1    (i >= 0) //succesful base clause
f(0,j) = 0    (j != 0) //non succesful base clause
f(i,j) = f(i-1,j) + f(i-1,j-arr[i])  //step

应用动态规划到上述递归公式，可以得到一个时间和空间复杂度为O(k*n)的解决方案。以f(n,k)为参数调用[假设数组索引从1开始]。

- amit

---

使用距离列表可以帮助计算 L={1,2,3,0,-3,-5,-6} g=2，那么 D(g,L) = {-1,0,+1,-2,-5,-7,-8}。 - Khaled.K

但是该算法不会计算子集的数量，它只会告诉你是否存在解决方案。即使在此基础上应用回溯算法，您也只能得出一个解决方案，而不是所有的解决方案。 - Amir Hossein F

Answer 2

以下是记忆化动态规划代码，用于打印给定总和的子集数量计数。 DP的重复值存储在“tmp”数组中。为了获得DP解决方案，始终从问题的递归解决方案开始，然后将重复值存储在tmp数组中，以获得记忆化解决方案。

#include <bits/stdc++.h>

using namespace std; 

int tmp[1001][1001];  


int subset_count(int* arr, int sum, int n) 
{ ` if(sum==0)
        return 1;
    if(n==0)
        return 0;
    if(tmp[n][sum]!=-1)
        return tmp[n][sum];
    else{
        if(arr[n-1]>sum)
            return tmp[n][sum]=subset_count(arr,sum, n-1);
        else{
            return tmp[n][required_sum]=subset_count(arr,sum, n- 1)+subset_count(arr,sum-arr[n-1], n-1);`
        }
    }
} 

// Driver code 

int main() 
{ ` memset(tmp,-1,sizeof(tmp));
    int arr[] = { 2, 3, 5, 6, 8, 10 }; 
    int n = sizeof(arr) / sizeof(int); 
    int sum = 10; `


    cout << subset_count(arr,sum, n); 

    return 0; 
}

- 927tanmay

Answer 3

虽然上述基本情况在约束条件为：1<=v[i]<=1000时可以正常工作

但是考虑到：约束条件：0<=v[i]<=1000

上述基本情况将会给出错误的答案，考虑一个测试用例：v = [0,0,1] 和 k = 1，根据基本情况，输出将会是"1"。

但是正确的答案是3：{0,1}{0,0,1}{1}

为了避免这种情况，我们可以深入探究而不是返回0，并通过以下方式进行修复：

C++:

if(ind==0)
{
if(v[0]==target and target==0)return 2;  
if(v[0]==target || target==0)return 1; 
return 0 ;
}

- Ravi

Answer 4

int numSubseq(vector<int>& nums, int target) {
    int size = nums.size();
    int T[size+1][target+1];
    for(int i=0;i<=size;i++){
        for(int j=0;j<=target;j++){
            if(i==0 && j!=0)
                T[i][j]=0;
            else if(j==0)
                T[i][j] = 1;
        }
    }
    for(int i=1;i<=size;i++){
        for(int j=1;j<=target;j++){
            if(nums[i-1] <= j)
                T[i][j] = T[i-1][j] + T[i-1][j-nums[i-1]];
            else
                T[i][j] = T[i-1][j];
        }
    }
    return T[size][target];
}

- Vansh Patpatia

Answer 5

这是一个递归解决方案。它的时间复杂度为O(2^n)。 使用动态规划来改进时间复杂度，使其变为二次的O(n^2)。

def count_of_subset(arr,sum,n,count):
    if sum==0:
        count+=1
        return count
    if n==0 and sum!=0:
        count+=0
        return count
    if arr[n-1]<=sum:
        count=count_of_subset(arr,sum-arr[n-1],n-1,count)
        count=count_of_subset(arr,sum,n-1,count)
        return count
    else:
        count=count_of_subset(arr,sum,n-1,count)
        return count

- harshit rathod

---

这是O(n^2)时间复杂度还是O(n*sum)？ - gsb22

它是二次时间，即O(2^n)，因为它是一种递归解决方案，会一遍又一遍地计算相同的问题。 - harshit rathod

你的意思是指数吗？二次方是2的幂。 - gsb22

@GauriShankarBadola 是的！ - harshit rathod

Answer 6

这个问题的一个解决方案是生成N的幂集，其中N是数组的大小，将等于2^n。对于0到2^N-1之间的每个数字，检查其二进制表示，并包括所有位于集合位置即为1的数组值。 检查是否所有包含的值的总和等于所需值。 这可能不是最有效的解决方案，但由于这是一个NP难问题，因此不存在多项式时间解决方案。

- rawatadit

---

这是一个天真的解决方案，不是最优的！ - skrtbhtngr