How to Solve Subset Sum Problem?

Board Infinity -

Introduction

Finding a subset' of the provided array A = (A1 A2 A3...An), in which the items of the array A are n positive integers, in such a way that a'A and the sum of the elements of such a subsets is equal to a certain positive integer S, is the goal of the subset-sum problem. This is a NP-hard problem. Given that there are several strategies for addressing it, subset-sum is an optimizing issue. With a manageable time complexity, subsets can be handled using dynamic programming and backtracking.

Problem Statement: Determine if there is a non-empty subset of the positive set of integers that sums to the number k.

Input:

A = { 3, 7, 8, 5, 2 }

k = 14

Output: Subset with sum=14 exists  -> Subset { 7, 2, 5 } sums to 14

Efficient Dynamic Approach

  • A dynamic approach to problem resolution would be ideal for such issues.
  • By starting with smaller subproblems and working our way up, we can solve larger subproblems.
  • If a subset with sum j can be discovered using items up to the first I items, the bottom-up method that follows computes T[i][j] for each 1 = I = n and 1 = j = sum is true.
  • It makes use of the previously computed lower values of I and j to prevent repeated calculations, hence reducing the time complexity.

Implementation Code

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


bool subsetSum(vector<int> const &A, int k)
{
    // total number of items
    int n = A.size();
    bool T[n + 1][k + 1];

    for (int j = 1; j <= k; j++) {
        T[0][j] = false;
    }


    //handling the case when the sum is zero
    for (int i = 0; i <= n; i++) {
        T[i][0] = true;
    }


    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
                if (A[i - 1] > j) {
                T[i][j] = T[i - 1][j];
            }
            else {
                T[i][j] = T[i - 1][j] || T[i - 1][j - A[i - 1]];
            }
        }
    }

    return T[n][k];
}


int main()
{
    vector<int> A = { 7, 3, 2, 5, 8 };
    int k = 18; // sum
   

    if (subsetSum(A, k)) {
        cout << "Subsequence with the given sum exists";
    }
    else {
        cout << "Subsequence with the given sum does not exist";
    }


    return 0;
}

Output: Subsequence with the given sum exists

write your code here: Coding Playground

Complexity Analysis

Time Complexity: O(N * sum)

Here, N = size of the array.

Space Complexity: O(N * sum)

Here, N = size of the array.