介绍

给定一个长度为 N 的数组 arr [] 和一个整数 X，任务是找出总和等于 X 的子集的数量。

一个简单的方法是通过生成所有可能的子集来解决这个问题，然后检查子集是否具有所需的和。这种方法的时间复杂度将是指数级的。

// Naive Approach

#include <stdio.h>

void printBool(int n, int len) {

 while (n) {
  if (n & 1) printf("1 ");
  else printf("0 ");
  n >>= 1;
  len--;
 }

 // This is used for padding zeros
 while (len) {
  printf("0 ");
  len--;
 }
 printf("\n");
}

// Function Prints all the subsets of given set[]
void printSubsetsCount(int set[], int n, int val) {
 int sum; // it stores the current sum
 int count = 0;
 for (int i = 0; i < (1 << n); i++) {
  sum = 0;
  // Print current subset
  for (int j = 0; j < n; j++)

   // (1<<j) is a number with jth bit 1
   // so when we 'and' them with the subset number we get which numbers are present in the subset and which are not
   // Refer: https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/?ref=lbp
   if ((i & (1 << j)) > 0) {
    sum += set[j]; // elements are added one by one of a subset to the sum
   }
  // It checks if the sum is equal to desired sum. If
  // it is true then it prints the elements of the sum
  // to the output
  if (sum == val) {
   /*
   * Uncomment printBool(i,n) to get the boolean
   * representation of the selected elements from
   * set. For this example output of this
   * representation will be 0 1 1 1 0 // 2,3,4
   * makes sum 9 1 0 1 0 1 // 1,3,5 also makes sum
   * 9 0 0 0 1 1 // 4,5 also makes sum 9
   *
   * 'i' is used for 'and' operation so the
   * position of set bits in 'i' will be the
   * selected element. and as we have to give
   * padding with zeros to represent the complete
   * set , so length of the set ('n') is passed to
   * the function.
   * */
   // printBool(i,n);
   count++;
  }
 }
 // it means no subset is found with given sum
 if (count == 0) printf("No subset is found");
 else printf("%d", count);
}

// Driver code
void main() {
 int set[] = { 1, 2, 3, 4, 5 };
 printSubsetsCount(set, 5, 9);
}

然而，对于较小的 X 值和数组元素，这个问题可以用动态规划来解决。我们先看一下递归关系。这个方法对所有的整数都有效。

dp[i][C] = dp[i - 1][C - arr[i]] + dp[i - 1][C] 

现在我们来了解一下 DP 的状态。这里， dp[i][C] 存储了子数组 arr[i...N-1] 的子集数量，使得它们的总和等于 C。因此，递归是非常琐碎的，因为只有两个选择，即要么考虑子集中的第 i 个元素，要么不考虑。

// Javascript implementation of the approach
const maxN = 20
const maxSum = 50
const minSum = 50
const base = 50
 
// To store the states of DP
const dp = Array.from(Array(maxN), ()=>Array(maxSum+minSum));
const v = Array.from(Array(maxN), ()=>Array(maxSum+minSum));
 
// Function to return the required count
function findCnt(arr, i, required_sum, n) {
  // Base case
  if (i == n) {
    if (required_sum == 0) return 1;
    return 0;
  }
  // If the state has been solved before return the value of the state
  if (v[i][required_sum + base]) return dp[i][required_sum + base];
  // Setting the state as solved
  v[i][required_sum + base] = 1;
  // Recurrence relation
  dp[i][required_sum + base] = findCnt(arr, i + 1, required_sum, n) + findCnt(arr, i + 1, required_sum - arr[i], n);
  return dp[i][required_sum + base];
}

使用制表法：

这个方法只对那些包含正数元素的数组有效。在这个方法中，我们使用一个大小为 (arr.size() + 1) * (target + 1) 的整数类型的二维数组。 矩阵的初始化： mat[0][0] = 1 因为如果总和为 0，那么存在总和为 0 的空子集 {}。

if (A[i] > j) DP[i][j] = DP[i-1][j]
else DP[i][j] = DP[i-1][j] + DP[i-1][j-A[i]]

这意味着，如果当前元素的值大于 "当前总和值"，我们将复制以前案例的答案。而如果当前的和值大于 ' 第 1 个 ' 元素，我们将看到之前的任何状态是否已经经历了 sum='j'，以及任何之前的状态经历了一个值 'j-A [i]'。

function subsetSum( a,  n, sum) {
  // Initializing the matrix
  var tab = new Array(n + 1);
  for (let i = 0; i< n+1; i++) tab[i] = new Array(sum + 1);
  // Initializing the first value of matrix
  tab[0][0] = 1;
  for (let i = 1; i <= sum; i++) tab[0][i] = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= sum; j++) {
      // if the value is greater than the sum
      if (a[i - 1] > j) tab[i][j] = tab[i - 1][j];
      else tab[i][j] = tab[i - 1][j] + tab[i - 1][j - a[i - 1]];
    }
  }

  return tab[n][sum];
}

时间复杂度：O (sumn)，其中 sum 是 "目标和"，"n" 是数组的大小。 辅助空间：O (sumn)，因为二维阵列的大小是 sum*n。

空间优化：

我们可以通过关注最后的状态和当前的状态来解决这个问题，所以我们可以在 O (target+1) 的空间复杂度下解决问题。

#include <bits/stdc++.h>
using namespace std;

int CountSubsetSum(vector<int>& arr, int val, int n) {
 int count = 0;
 vector<int> PresentState(val + 1, 0),
 LastState(val + 1, 0);
 // consider only last and present state we dont need the (present-2)th state and above and we know for val to be 0 if we dont pick the current index element we can achieve
 PresentState[0] = LastState[0] = 1;
 if (arr[0] <= val) LastState[arr[0]] = 1;
 for (int i = 1; i < n; i++) {
  for (int j = 1; j <= val; j++)
   PresentState[j] = ((j >= arr[i]) ? LastState[j - arr[i]] : 0) + LastState[j];
   // this we will need in the next iteration so just swap current and last state.
   LastState = PresentState;
 }
 // Note after exit from loop we will having a present state which is nothing but the laststate itself;
 return PresentState[val]; // or return CurrentState[val];
}
int main() {
 vector<int> arr = { 3, 3, 3, 3 };
 cout << CountSubsetSum(arr, 6, arr.size());
}

实现

JavaScript

/*
Given an array of non-negative integers and a value sum,
determine the total number of the subset with sum equal to the given sum.
*/
/* Given solution is O(n*sum) Time complexity and O(sum) Space complexity */
function NumberOfSubsetSum (array, sum) {
  const dp = [] // create an dp array where dp[i] denote number of subset with sum equal to i
  for (let i = 1; i <= sum; i++) dp[i] = 0
  dp[0] = 1 // since sum equal to 0 is always possible with no element in subset

  for (let i = 0; i < array.length; i++) {
    for (let j = sum; j >= array[i]; j--) {
      if (j - array[i] >= 0) dp[j] += dp[j - array[i]]
    }
  }
  return dp[sum]
}

参考

• Count of subsets with sum equal to X - GeeksforGeeks (opens new window)