Of course the naïve solution would be to generate all possible subsets and check their sum equals to K or not. But it would of course be computationally exponential to generate all possible subsets.

To do so, the recursion would be:

For nth element the cases are:

1. Consider the nth element as part of solution subset and recur for n-1 elements for obtaining sum (K-arr[n]).
2. Don't consider nth element as part of solution subset and recur for n-1 elements for obtaining sum (K).

So, the recursion function can be written as:

    f(n,K)=f(n-1,K) | f(n-1,K-arr[n-1])

Where,

    f(n,K)= value for problem with array size n and sum K which can be either true or false

Now base case would be,

Here comes the concept of sub problem. Initially the problem is for size n and sum K. Then it gets reduced to {size (n-1) and sum K} or {size (n-1) and (sum K-arr[n-1])}

So if you draw the recursion tree there will be many such sub-problem which will be overlapping ones. That means we will re-compute same sub-problems again and again. That’s why we need to store the value of sub-problems and use dynamic programming.

Converting to dynamic programming:

    1)  Initialize  dp[n+1][sum+1] which is a Boolean table to false
    2)  Convert the base cases for recursion
        for i=1 to sum
            dp[0][i]=false;
        for i=0 to n
            dp[i][0]=true;
    3)  Build the table as per the recursion formula.
        for i=1 to sum
            for j=1 to n
                //if sub-sum i>jth element then only we can take that
                if(i>=arr[j-1])   
                    //consider both case mentioned in solution approach
                    dp[j][i]=dp[j-1][i] | dp[j-1][i-arr[j-1]];   
                else                       // don't take jth element
                    dp[j][i]=dp[j-1][i];

                if(i==sum)
                    if(dp[j][i]){
                        return true;
                End If
            end for
        end for

    4)  If not returned from the loop  
            return false;

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

bool subsetSum(vector<int> arr, int n, int sum)
{
    //DP matrix
    bool dp[n + 1][sum + 1];

    memset(dp, false, sizeof(dp));

    //base case
    for (int i = 1; i <= sum; i++)
        dp[0][i] = false;
	
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;
	
    //build the table
    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= arr[j - 1])
                dp[j][i] = dp[j - 1][i] | dp[j - 1][i - arr[j - 1]];
            else
                dp[j][i] = dp[j - 1][i];

            if (i == sum) {
                if (dp[j][i]) {

                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int t, n, k, item;
	
    cout << "Enter array length,n\n";
    cin >> n;
	
    cout << "Enter sum,K\n";
    cin >> k;
	
    cout << "Enter elements\n";
    vector<int> a;
    for (int j = 0; j < n; j++) {
        scanf("%d", &item);
        a.push_back(item);
    }

    if (subsetSum(a, n, k))
        cout << "yes\n";
    else
        cout << "no\n";

    return 0;
}

Output

RUN 1:
Enter array length,n
5
Enter sum,K
11
Enter elements
5 6 7 3 9
yes

RUN 2:
Enter array length,n
5
Enter sum,K
22
Enter elements
5 6 7 3 9
yes