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;
}