Home » Interview coding problems/challenges

# Subset Sum

**Subset Sum**: Here, we are going to learn **how to solve the subset sum problem which has been featured in many interview rounds like Amazon, Microsoft?**

Submitted by Radib Kar, on February 29, 2020

**Description:**

In this article, we are going to see **how to solve the subset sum problem** which has been featured in many interview rounds like Amazon, Microsoft?

**Problem statement:**

Given an array of size **n** and a sum **K**, determine whether any subset is possible with that sum or not. Print **"yes"** if there is any subset present else print **"no"**.

Input & output: In the first line the input will be n and K, space separated. The next line contains the array elements Output will be "yes" or "no"

**Example with explanation:**

**Example 1:**

Input: The array size be: 5 The sum be: 11 The Elements be: 5 6 7 3 9 Output: Yes Explanation: 5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".

**Example 2:**

Input: The array size be: 5 The sum be: 11 The Elements be: 5 6 7 3 9 Output: Yes Explanation: 5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".

**Solution Approach:**

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 n_{th} element the cases are:

- Consider the n
^{th}element as part of solution subset and recur for n-1 elements for obtaining sum (K-arr[n]). - Don't consider n
^{th}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,

f(0,0) = true f(0,i) = false for 1 ≤ i ≤K f(i,0) = true 1 ≤ i ≤ n

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions