Subset Sum Problem - C++ Solution

1. Introduction

In this blog post, we explore the Subset Sum Problem, a fundamental problem in computer science and dynamic programming. The challenge is to determine whether there's a subset of a given set of positive integers that sums to a specific target value k.

Problem

Given a set of positive integers and an integer k, the task is to check if there exists any non-empty subset of the set that sums to k.

Example:

Input: nums = [7, 3, 2, 5, 8], k = 14

Output: true

Explanation: The subset [7, 2, 5] sums to 14.

2. Solution Steps

1. Use dynamic programming to create a table that keeps track of possible sums up to k using the numbers in the array.

2. Initialize the first column of the table (sum = 0) as true, since the sum of 0 can always be achieved with no elements.

3. Fill in the table by checking for each number if the sum can be achieved either by including or excluding the current number.

4. The answer will be in the last cell of the table, indicating if the sum k is achievable.

3. Code Program

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

bool subsetSum(vector<int>& nums, int k) {
    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(k + 1, false));

    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; 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];
            }
        }
    }

    return dp[n][k];
}

int main() {
    vector<int> nums = {7, 3, 2, 5, 8};
    int k = 14;
    cout << "Subset sum to " << k << ": " << boolalpha << subsetSum(nums, k) << endl;
    return 0;
}

Output:

Subset sum to 14: true

Explanation:

The subsetSum function creates a 2D dynamic programming array dp, where dp[i][j] is true if a subset of the first i numbers can sum up to j. It iterates through each number, updating the dp table based on whether including or excluding the current number can achieve the sum j. The final answer is found in dp[n][k], indicating whether a subset sum to k is achievable with the given set of numbers. This approach efficiently solves the subset sum problem, as demonstrated in the output for the given example.