Array Dynamic Programming Tabulation
Proficient Level

Implement the countSubsetSumWays method that counts how many subsets produce the target sum.

The input contains an integer array nums, its length size, and a target value target. Your task is to count how many subsets have a sum exactly equal to the target.

Each element is treated by its position, so duplicate values can form different subsets. For example, in [1,2,3,3] with target 6, there are 3 valid subsets.

Example 1
Input:
nums (int[]) = [1,2,3,3]
size (int) = 4
target (int) = 6
Return:
(int) 3
Example 2
Input:
nums (int[]) = [1,1,1]
size (int) = 3
target (int) = 2
Return:
(int) 3
Example 3
Input:
nums (int[]) = [2,4]
size (int) = 2
target (int) = 5
Return:
(int) 0

Use dynamic programming where dp[x] stores how many subsets can make sum x.

Start with dp[0] = 1, because there is one way to make zero: choose no elements. For each number, update sums from target down to the number.

The backward loop makes sure each element is counted at most once. After all numbers are processed, dp[target] contains the required count.

Pseudocode:

function countSubsetSumWays(nums, size, target):
    dp = array of target + 1 values filled with 0
    dp[0] = 1
    for each num in nums:
        for sumValue from target down to num:
            dp[sumValue] = dp[sumValue] + dp[sumValue - num]
    return dp[target]
Run your code to see the result.