Subset Sum

December 7, 2021

Subset Sum

The subset sum problem is a variation of the 01 knapsack problem. In this problem, we have to pick elements such that the sum of elements is equal to the given sum. In this article, we provide a c++ solution with an explanation.

Subset Sum Problem Description

Subset Sum Problem Description

Given an array of n integers. We are also given a element x. We have to pick some elements from the array elements  such that the sum of picked elements is equal to x.

Determine whether it is possible or not.

Input

  • First line contains an integer n – the number of integers.
  • Second line contains single integer – x.
  • Next line contains n integers – the elements of an array.

Output

  • Single line output Yes if possible otherwise No.

Subset Sum Problem Solution

Prerequisites – 0-1 Knapsack Problem

This problem is variation of 0-1 Knapsack. To understand better we can rephrase question as find if we can pick items of some weight such that sum of weight of the picked items is equal to the capacity of the knapsack (x).

The problem has the same exact solution as the 0-1 knapsack problem with some miner changes. Refer to code below.

Time Complexity – O(n*x)

Space Complexity – O(n*x)

Code

#include <bits/stdc++.h>
using namespace std;
bool subsetSum(int arr[], int n, int sum)
{
    int W = sum;
    bool dp[n + 1][W + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0) // Base Case
                dp[i][w] = true;
            else if (arr[i – 1] > w) // We cannot include ith item
                dp[i][w] = dp[i – 1][w];
            else // We can include ith item
                dp[i][w] = dp[i – 1][w – arr[i – 1]] || dp[i – 1][w];
        }
    }
    return dp[n][W];
}

int main()
{
    int n = 6;
    int arr[n] = {1, 5, 1, 2, 3, 2};
    int sum = 8;
    if (subsetSum(arr, n, sum))
        cout << “Yes” << endl;
    else
        cout << “No” << endl;

    return 0;
}

Output

Yes
Explanation
5 + 1+ 2 = 8