Dynamic Programming (P1)

The Subset Sum is a classic problem in Dynamic Programming (DP). It is used to determine whether there exists a subset of a given set of numbers that sums up to a specific target value. This is a problem commonly encountered in areas like partitioning problems, knapsack problems, and combinatorial optimization.

Problem Description:

Given a set of integers, you need to determine whether there exists a subset whose sum is equal to a specific target value.

Example:

• Input:nums = [2, 3, 7, 8, 10] , target = 11

• Output: True

  • There exists a subset of nums that adds up to 11, for example: [3, 8] or[2, 3, 7].

• Input: nums = [1, 2, 3, 9], target = 8

• Output: False

  • No subset sums to 8.

Approach (Dynamic Programming):

1. Define the Problem:

• We want to know if there is a subset of the numbers in the array that sums up to the given target.

2. State Representation:

• Let dp[i] represent whether a subset sum of i is achievable using any subset of the numbers in the array.

• Initialize dp[0]= true because a sum of 0 is always achievable (the empty subset).

3. Transition:

For each number in the array, we update the dp array in reverse order. For each i, if dp[i - num] is true (i.e., if i - num can be achieved), then set dp[i]to true.

4. Final Answer:

The answer is stored in dp[target]. If dp[target] is true, then there is a subset whose sum is equal to the target.

C++ Solution Example:

#include <iostream>
#include <vector>
using namespace std;

bool subsetSum(const vector<int>& nums, int target) {
    vector<bool> dp(target + 1, false);  // DP array initialized to false
    dp[0] = true;  // Sum of 0 is always possible with an empty subset

    for (int num : nums) {
        for (int i = target; i >= num; --i) {
            dp[i] = dp[i] || dp[i - num];  // If dp[i-num] is true, set dp[i] to true
        }
    }

    return dp[target];  // Return if the target sum is achievable
}

int main() {
    vector<int> nums = {2, 3, 7, 8, 10};
    int target = 11;

    if (subsetSum(nums, target)) {
        cout << "There is a subset with sum " << target << endl;
    } else {
        cout << "There is no subset with sum " << target << endl;
    }

    return 0;
}