Array Dynamic Programming Tabulation
Intermediate Level

Implement the subsetSumExists method that checks whether any subset can produce the target sum.

The input contains an integer array nums, its length size, and a target value target. Your task is to check whether any subset of the array has a sum equal to the target.

Each element can be used at most once. For example, in [3,34,4,12,5,2] with target 9, the subset [4,5] makes 9, so the answer is true.

Example 1
Input:
nums (int[]) = [3,34,4,12,5,2]
size (int) = 6
target (int) = 9
Return:
(boolean) true
Example 2
Input:
nums (int[]) = [1,2,3]
size (int) = 3
target (int) = 7
Return:
(boolean) false
Example 3
Input:
nums (int[]) = [2,4,6]
size (int) = 3
target (int) = 6
Return:
(boolean) true

Use dynamic programming to track which sums are possible.

Create a boolean array where dp[x] means a subset with sum x can be formed. Start with dp[0] = true, because sum zero is possible by choosing no elements.

For each number, update the possible sums in reverse order. Reverse order is important because one number should not be reused multiple times in the same step.

Pseudocode:

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