计数具有给定和的子集的数目

Question

我正在尝试解决给定和leetcode的子集计数问题，我的代码在大多数测试用例中都能很好地工作，但它不能处理数组中出现"0"的情况。

例如：arr[] :{0,0,0,0,1,0,0,0,0}、sum: 1

这里的输出应该是256。

这是我的代码：

private int[][] dp;
/** nums => input array
n => nums.length-1
sum => target sum
**/
public int findNoOfSubset(int[] nums, int n, int sum) {
//System.out.println(n  +" " + sum);
if(sum == 0){
return 1;
}

if(n < 0 || sum < 0) {
return 0;
}

if(dp[n][sum] != -1) {
return dp[n][sum];
}

if(sum >= nums[n]) {
return dp[n][sum] = findNoOfSubset(nums, n-1, sum-nums[n]) + findNoOfSubset(nums, n-1, sum);
}

return dp[n][sum] = findNoOfSubset(nums, n-1, sum);
}

有人能指导我如何处理0元素的情况吗。

Answer 1

看待这个问题的另一种方法是找到子集和的方法。

// Create a map with key as the sum of a subset and value as the number of ways this sum was found.
Map<Integer, Integer> m = new HashMap<>(); 
// initialising as 0 can be found by selecting no numbers 
primary.put(0,0);
for (Integer i : numbers) {
List<Integer> newSums = new ArrayList<>();
for (Integer possibleSum : m.keySet()) {
if (i+possibleSum > targetSum)
continue;
newSums.add(i+possibleSum);
}
for (Integer newPossibleSum : newSums) {
m.put(newPossibleSum, m.getOrDefault(newPossibleSum, 0)+1);
} 
}
return m.getOrDefault(targetSum,0);

Answer 2

我发现了我的错误，只是发布了解决方案，以防有人遇到同样的问题。

public int findNoOfSubset(int[] nums, int n, int sum) {
if(sum == 0 && n<0){
return 1;
}

if(n < 0 || sum < 0) {
return 0;
}

if(dp[n][sum] != -1) {
return dp[n][sum];
}

if(sum >= nums[n]) {
return dp[n][sum] = findNoOfSubset(nums, n-1, sum-nums[n]) + findNoOfSubset(nums, n-1, sum);
}

return dp[n][sum] = findNoOfSubset(nums, n-1, sum);
}

Answer 3

int getSubsetwithsumk(int arr[], int n, int k) {
int t[n+1][k+1];
//initialisation
for(int i = 0 ; i < n + 1 ; i++){
for(int j = 0 ; j < k + 1 ; j++){
if(i == 0){
t[i][j] = 0;
}
if(j == 0){
t[i][j] = 1;
}
}
}
for(int i = 1 ; i < n + 1 ; i++){
for(int j = 1 ; j < k + 1 ; j++){
if(arr[i-1] <= j)
t[i][j] = t[i-1][j - arr[i-1]] + t[i-1][j];
else{
t[i][j] = t[i-1][j];
}  
}
}
return t[n][k];

}