# 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**

**Complexity Analysis**

**Time Complexity**: O(N * sum)

Here, N = size of the array.**Space Complexity:** O(N * sum)

Here, N = size of the array.