The Subset Sum Problem is a classic problem in computer science and combinatorial optimization. It aims to determine whether there exists a subset of a given set of integers that adds up to a specific target sum.

Program Structure

• Input: A set of integers and a target sum.
• Output: A boolean value indicating whether a subset with the given sum exists.
• Dynamic Programming: The program uses a 2D array to store the results of subproblems.

C++ Code

#include <iostream>
#include <vector>

using namespace std;

// Function to determine if a subset with the given sum exists
bool subsetSum(const vector<int>& nums, int target) {
    int n = nums.size();
    
    // Create a 2D vector to store the results of subproblems
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));

    // Base case: A sum of 0 can always be formed with an empty subset
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // Fill the dp array
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            if (nums[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // The answer will be in dp[n][target]
    return dp[n][target];
}

int main() {
    int n, target;

    // Input number of elements and the target sum
    cout << "Enter number of elements in the set: ";
    cin >> n;
    vector<int> nums(n);

    cout << "Enter the elements of the set: ";
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    cout << "Enter the target sum: ";
    cin >> target;

    // Determine if a subset with the given sum exists
    if (subsetSum(nums, target)) {
        cout << "A subset with the given sum exists." << endl;
    } else {
        cout << "No subset with the given sum exists." << endl;
    }

    return 0;
}

Explanation of the Code

The code consists of the following main components:

• Input Handling: The program prompts the user to enter the number of elements in the set, the elements themselves, and the target sum.
• Subset Sum Calculation: The subsetSum function uses dynamic programming to fill a 2D vector dp. Here, dp[i][j] holds a boolean value indicating whether a subset of the first i elements can sum to j.
• Initialization: The first column of the dp table is initialized to true since a sum of 0 can always be achieved with an empty subset.
• Dynamic Programming Logic: For each number, the function checks if it can be included in the subset to reach the target sum and updates the dp table accordingly.
• Output: The program displays whether a subset with the given sum exists based on the final value in the dp table.

Conclusion

This program efficiently determines if there exists a subset of a given set that sums to a specific target using dynamic programming techniques, making it a useful algorithm in combinatorial optimization.