求解数字和为sum的方法数问题。给定一个有n个正整数的数组a和一个整数sum，求选择数组a中部分数字和为sum的方案数。若两种选取方案有一个数字的下标不一样，则认为是不同的方案。

这是一个经典的背包问题，可以使用动态规划来解决。

定义一个二维数组dp，其中dp[i][j]表示在前i个数字中选取若干个数字，使得它们的和恰好为j的方案数。

初始化dp数组，当j为0时，dp[i][0]都为1，表示不选取任何数字的方案数为1。

接下来，对于每个数字a[i]，考虑两种情况：

1. 不选取a[i]，此时dp[i][j]的值与dp[i-1][j]相同；

2. 选取a[i]，此时dp[i][j]的值等于dp[i-1][j-a[i]]，表示在前i-1个数字中选取若干个数字，使得它们的和恰好为j-a[i]，再加上选取a[i]这一个数字的方案数。

最终，dp[n][sum]即为所求的答案。

时间复杂度为O(n*sum)。

相关问题

输入一串n个正整数的数组以及一个正整数 C，使用c语音

输入一串n个正整数的数组以及一个正整数C，通常是指在一个编程任务中，你需要处理一个问题，比如求解某个满足特定条件的子数组之和恰好等于给定的目标值C。这个过程被称为“查找总和为C的子数组”或者“数组元素之和等于目标值的问题”。常见的算法如哈希表法或前缀和（prefix sum）可以用来解决这个问题，通过遍历数组，计算每个位置到结尾的子数组和，然后检查是否有一个子数组和等于C。

例如，在Python中，你可以这样做：

def subarraySum(nums, target):
    prefix_sum = [0] * (len(nums) + 1)
    for i in range(1, len(prefix_sum)):
        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
    
    count = 0
    for i in range(len(prefix_sum)):
        j = len(prefix_sum) - 1
        while i < j and prefix_sum[j] > target:
            j -= 1
        if i <= j and prefix_sum[j] == target:
            count += 1
    
    return count

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。请用c++写一段求解程序

这个问题可以转化为一个 0/1 背包问题：给定一个只包含正整数的非空数组 nums，要求从 nums 中选取一些数，使得它们的和恰好为 nums 中所有数的和的一半。

C++ 代码如下：

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0) return false; // 总和为奇数，无法分成两个和相等的子集
    int n = nums.size();
    int target = sum / 2;
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    // dp[i][j] 表示 nums[0...i-1] 中是否存在子集的和为 j
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true; // 目标和为 0，任何子集都可以满足
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= target; ++j) {
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][target];
}

int main() {
    vector<int> nums{1, 5, 11, 5};
    if (canPartition(nums)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

输出结果为：

Yes

时间复杂度为 $O(n \times target)$，其中 $n$ 是数组长度，$target$ 是数组元素和的一半。