Subset problem

The subset problem is one of the problems solved using backtracking. In this problem, we need to find the subset of elements that are selected from a given set whose sum adds up to a given number K, it is assumed that the set consists of non-negative values, and there are no duplicates present. 

One way of solving it is using the backtracking algorithm. 

We use exhaustive search to consider all subsets irrespective of whether they satisfy the given constraints or not. A systematic consideration is made using backtracking to select the elements. 

Let us understand it better by using an example. 

Let us take a set of 5 integers, {4, -2, 2, 1}. 

So, we need to find a subset whose sum is equal to 5. 

There can be many approaches to doing so, one method is the naive approach. Here we use a search that generates all the subsets of the original array, this approach will have 2n possibilities. The time complexity will also be exponentially higher. So, we consider all these subsets in O(N) linear time and check if the sum of the elements matches or not. 

Solving it using dynamic programming

Let us consider an array A, which consists of n number of non-negative elements. Find a subset X, so that the sum of all the elements equals the given number K. 

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

Sum = 14. 

We will start by creating a table with rows and columns i and j. 

Now, we will check for each element, starting with the element 2. If the sum is true we will use 1, and if the sum is false we will use 0. 

How do we check for the value?

We follow,

required sum = j- element. 
A[i] [j]= A[i-1] [sum]

Similarly we consider the element 3, 

After, we have filled for each element, it will be:

Reference

Subset problem