计数没有。给定总和的子集

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];
    
}

计数没有。给定总和的子集

Count no. of subsets with given sum

java

algorithm

dynamic-programming