给定一个数组,我们需要找出具有恰好等于给定整数k的和的子集数量。
请提供此问题的最优算法。这里不需要实际的子集只需要计数即可。
数组由负数和非负数整数组成。
例子: 数组 -> {1,4,-1,10,5} 绝对值和->9 答案应该是{4,5}和{-1,10},共2个子集。
数组由负数和非负数整数组成。
例子: 数组 -> {1,4,-1,10,5} 绝对值和->9 答案应该是{4,5}和{-1,10},共2个子集。
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
L={1,2,3,0,-3,-5,-6} g=2
,那么 D(g,L) = {-1,0,+1,-2,-5,-7,-8}
。 - Khaled.K#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;
}
虽然上述基本情况在约束条件为: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 ;
}
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];
}
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
这个问题的一个解决方案是生成N的幂集,其中N是数组的大小,将等于2^n。对于0到2^N-1之间的每个数字,检查其二进制表示,并包括所有位于集合位置即为1的数组值。 检查是否所有包含的值的总和等于所需值。 这可能不是最有效的解决方案,但由于这是一个NP难问题,因此不存在多项式时间解决方案。