# How to Solve Subset Sum Problem?

## 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 #include using namespace std;bool subsetSum(vector 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 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.