Subset Problem - Dynamic Problem
You are given a set of positive integers (0 included) and a sum integer. You have to find if there exists a subset whose sum is equal to the given integer or not. Print True if it exists; otherwise, print False.
Example 1
Input set[] = {1, 16, 4, 12, 6, 8}
sum = 7
Output: True
If you clearly see the example 1+6 = 7. Hence the output is True.
Example 2
Input set[] = {1, 16, 4, 12, 6, 8}
sum = 15
Output: False
There is no subset that adds up to 15. Hence the output is False
Approach 1: Recursion Approach
In this approach, we will be using recursion. We will break this problem into smaller subproblems recursively. If we look closely in the program we could have the following possible cases:
- Either, we can take the current integer in the subset. Then use recursion for the other elements that remained in the subset.
- Or we can exclude this element and again follow the recursion.
We have to check for both the cases which one satisfies our need and then print the output.
Algorithm
- Take a set as input.
- Check recursively. If the set is equal to NULL, return False, as there is no element in the set.
- If it is not equal to NULL, traverse the set recursively for the last element.
- Ignore the element if it is greater than the given sum integer.
-
If not, check if
- We can get the sum by including the last element.
- We can get the sum by excluding the last element.
- Include the last element and check for the subset in the set whose sum is equal to the given sum integer.
- If found, return True.
- If not, exclude the last element and again check in the set for the subset whose sum is equal to the given integer.
- Return True if the subset is found, else return False.
CPP
#include <iostream>
#include <stdio.h>
using namespace std;
// function to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// leave an element of the set[]
// if it is greater than the given sum.
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
// else find if a subset can be found by->
// considering the element at last index, and
// excluding the element at last index.
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
// Driver code
int main()
{
int set[] = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
cout << "True";
else
cout << "False";
return 0;
}
Output
True
JAVA
class Subset {
// method to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
static boolean isSubsetSum(int set[],
int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// leave an element of the set[]
// if it is greater than the given sum.
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
// else find if a subset can be found by->
// considering the element at last index, and
// excluding the element at last index.
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
/* Driver code */
public static void main(String args[])
{
int set[] = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("True");
else
System.out.println("False");
}
}
Output
True
Python
# function to find if a subset
# having sum as given sum exists or not.
# returns true if a valid subset is found.
def isSubsetSum(set, n, sum):
# Base Cases
if (sum == 0):
return True
if (n == 0):
return False
# leave an element of the set[]
# if it is greater than the given sum.
if (set[n - 1] > sum):
return isSubsetSum(set, n - 1, sum)
# else find if a subset can be found by->
# considering the element at last index, and
# excluding the element at last index.
return isSubsetSum(
set, n-1, sum) or isSubsetSum(
set, n-1, sum-set[n-1])
# Driver code
set = [4, 32, 6, 11, 9, 1]
sum = 10
n = len(set)
if (isSubsetSum(set, n, sum) == True):
print("True")
else:
print("False")
Output
True
Complexity Analysis
Time complexity: (exponential), as in the worst case, this approach will sum each number to every element. Hence its complexity is exponential. Space complexity: O(n*sum), where n is the number of elements and sum is the given sum integer.
Approach 2: Dynamic programming
Since the above approach is a no known polynomial-time approach, this approach is a better one as it solves this problem in a pseudo-polynomial time. Here, we are going to initialize a boolean 2-D Array. If the current element has a value greater than the current sum integer, we will consider the element for the previous elements. But if the current value has a value greater than than the ith value, we are going to check if any of the previous subsets satisfy the need and are equal to the given sum integer. Return true if the array has a subset that is equal to j (sum value).
Algorithm
- Create a 2-D set where i is the index of the set elements and j is the sum value.
- Return True if there exists a subset with a sum equal to i
- If the sum is equal to 0, return True.
- Return False if the set is empty.
- Check if the current element has a value greater than the current sum integer, we will consider the element for the previous elements.
- But if the current value has a value greater than than the ith value, we are going to check if any of the previous subsets satisfy the need and are equal to the given sum integer.
CPP
#include <iostream>
#include <stdio.h>
using namespace std;
// function to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
bool isSubsetSum(int set[], int n, int sum)
{
// to get a true value for subset[i][j]
// there must exist a subset of set[0...j-1]
// having sum equal to i.
bool subset[n + 1][sum + 1];
// result will be true
// if sum equals to 0.
for (int i = 0; i <= n; i++)
subset[i][0] = true;
// result will be false
// if the set is empty
// and the given sum equals to 0.
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
// tabulating the values in a
// bottom-up fashion.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1]) subset[i][j] = subset[i - 1][j]; if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j]
|| subset[i - 1][j - set[i - 1]];
}
}
return subset[n][sum];
}
// Driver code
int main()
{
int set[] = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
cout << "True";
else
cout << "False";
return 0;
}
Output
True
JAVA
class Subset {
// function to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
static boolean isSubsetSum(int set[],
int n, int sum)
{
// to get a true value for subset[i][j]
// there must exist a subset of set[0...j-1]
// having sum equal to i.
boolean subset[][] = new boolean[sum + 1][n + 1];
// result will be true
// if sum equals to 0.
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// result will be false
// if the set is empty
// and the given sum equals to 0.
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
// tabulating the values in a
// bottom-up fashion.
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) { subset[i][j] = subset[i][j - 1]; if (i >= set[j - 1])
subset[i][j] = subset[i][j]
|| subset[i - set[j - 1]][j - 1];
}
}
return subset[sum][n];
}
/* Driver code*/
public static void main(String args[])
{
int set[] = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("True");
else
System.out.println("False");
}
}
class Subset {
// function to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
static boolean isSubsetSum(int set[],
int n, int sum)
{
// to get a true value for subset[i][j]
// there must exist a subset of set[0...j-1]
// having sum equal to the given sum.
boolean subset[][] = new boolean[sum + 1][n + 1];
// result will be true
// if sum equals to 0.
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// result will be false
// if the set is empty
// and the given sum equals to 0.
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
// tabulating the values in a
// bottom-up fashion.
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) { subset[i][j] = subset[i][j - 1]; if (i >= set[j - 1])
subset[i][j] = subset[i][j]
|| subset[i - set[j - 1]][j - 1];
}
}
return subset[sum][n];
}
/* Driver code*/
public static void main(String args[])
{
int set[] = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("True");
else
System.out.println("False");
}
}
Output
True
Python
# function to find if a subset
# having sum as given sum exists or not.
# returns true if a valid subset if found.
def isSubsetSum(set, n, sum):
# to get a true value for subset[i][j]
# there must exist a subset of set[0...j-1]
# having sum equal to i.
subset =([[False for i in range(sum + 1)]
for i in range(n + 1)])
# result will be true
# if sum equals to 0.
for i in range(n + 1):
subset[i][0] = True
# result will be false
# if the set is empty
# and the given sum equals to 0.
for i in range(1, sum + 1):
subset[0][i]= False
# tabulating the values in a
# bottom-up fashion.
for i in range(1, n + 1):
for j in range(1, sum + 1):
if j<set[i-1]: subset[i][j] = subset[i-1][j] if j>= set[i-1]:
subset[i][j] = (subset[i-1][j] or
subset[i - 1][j-set[i-1]])
return subset[n][sum]
# Driver code
if __name__=='__main__':
set = [4, 32, 6, 11, 9, 1]
sum = 10
n = len(set)
if (isSubsetSum(set, n, sum) == True):
print("True")
else:
print("False")
Output
True
Complexity Analysis
Time complexity: Pseudo-polynomial time, which means that the code is running in a time that is polynomial, but unlike the polynomial-time complexity, it does not depend on the length of the input, rather it depends on the largest element of the input. Space complexity: O(n*sum), where n is the number of elements and sum is the given sum integer, as the matrix will take exactly n*sum extra space
Approach 3: Memoization Technique
This method is the most optimized and precise approach among all three approaches. In this approach, we have to break this problem into smaller subproblems and then again breaking these subproblems into smaller subproblems recursively. We will be using Dynamic Programming as well to avoid the repeated computation of subproblems and store them in the matrix.
Algorithm
- Create a 2-D array globally.
- Return False if the set is empty, or the sum becomes negative.
- Create a function to find if a subset having sum as a given sum exists or not returns true if a valid subset is found.
- Creating a key for a map having unique value using the elements of the input.
-
Store the result of the problem if it is encountered for the first time.
- Computing the result including the element at the last index.
- Computing the result excluding the element at the last index.
- Storing the result combining the above-computed results
CPP
#include
#include
using namespace std;
// map for storing subproblem solutions
unordered_map<string, bool> result;
// function to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
bool subsetSum(int arr[], int n, int sum)
{
// base cases
if (sum == 0) {
return true;
}
if (n < 0 || sum < 0) {
return false;
}
// creating a key for map
// having unique value
// using the elements of the input
string key = to_string(n) + "|" + to_string(sum);
// store the result of the problem in the map
// if it is encountered for the first time
if (result.find(key) == result.end())
{
// computing the result including the element
// at the last index
bool include = subsetSum(arr, n - 1, sum - arr[n]);
// computing the result excluding the element
// at the last index
bool exclude = subsetSum(arr, n - 1, sum);
// storing the result combining the above computed results
result[key] = include || exclude;
}
// returning the above result
return result[key];
}
// Subset Sum Problem
int main()
{
// Input: a set of items and a sum
int arr[] = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
int n = sizeof(arr) / sizeof(arr[0]);
if (subsetSum(arr, n - 1, sum)) {
cout << "True";
}
else {
cout << "False";
}
return 0;
}
Output
True
JAVA
import java.util.HashMap;
import java.util.Map;
class Subset
{
// method to find if a subset
// having sum as given sum exists or not.
// returns true if a valid subset is found.
public static boolean subsetSum(int[] A, int n, int sum,
Map<String, Boolean> result)
{
// base cases
if (sum == 0) {
return true;
}
if (n < 0 || sum < 0) {
return false;
}
// creating a key for map
// having unique value
// using the elements of the input
String key = n + "|" + sum;
// store the result of the problem in the map
// if it is encountered for the first time
if (!result.containsKey(key))
{
// computing the result including the element
// at the last index
boolean include = subsetSum(A, n - 1, sum - A[n], result);
// computing the result excluding the element
// at the last index
boolean exclude = subsetSum(A, n - 1, sum, result);
// storing the result combining the above computed results
result.put(key, include || exclude);
}
// returning the above result
return result.get(key);
}
public static void main(String[] args)
{
// Input: a set of items and a sum
int[] A = { 4, 32, 6, 11, 9, 1 };
int sum = 10;
// create a map to store solutions to subproblems
Map<String, Boolean> result = new HashMap<>();
if (subsetSum(A, A.length - 1, sum, result)) {
System.out.println("True");
}
else {
System.out.println("False");
}
}
}
Output
True
Python
# function to find if a subset
# having sum as given sum exists or not.
# returns true if a valid subset if found.
def subsetSum(A, n, sum, result):
# base cases
if sum == 0:
return True
if n < 0 or sum < 0:
return False
# creating a key for map
# having unique value
# using the elements of the input
key = (n, sum)
# store the result of the problem in the map
# if it is encountered for the first time
if key not in result:
# computing the result including the element
# at the last index
include = subsetSum(A, n - 1, sum - A[n], result)
# computing the result excluding the element
# at the last index
exclude = subsetSum(A, n - 1, sum, result)
# storing the result combining the above-computed results
result[key] = include or exclude
# returning the above result
return result[key]
if __name__ == '__main__':
# Input: a set of items and a sum
A = [4, 32, 6, 11, 9, 1]
sum = 10
# create a dictionary to store solutions to subproblems
result = {}
if subsetSum(A, len(A) - 1, sum, result):
print("True")
else:
print("False")
Output
True
Complexity Analysis
Time complexity: O(n*sum), where n is the number of elements and sum is the given sum integer. Space complexity: O(n*sum), where n is the number of elements and sum is the given sum integer, as the matrix will take exactly n*sum extra space
Conclusion
In this article, we have learned an amazing concept of Binary Trees. Binary Tree is one of the most important data structures and is usually asked in the top interview questions as well. “Finding ancestral nodes of a given node” is a popular as well as a very important problem that has been asked in various interview questions. In this article, we have skimmed about what are the ancestor nodes in Binary Trees and how we can get the ancestor nodes of a given node in a detailed as well as well-explained manner. We have included proper diagrams of trees for a better understanding of the readers. We also learned about what is post-order traversal and how it will be beneficial over other traversals i.e., inorder traversal and preorder traversal in such kinds of problems. We also discussed three well-explained approaches along with some suitable examples to solve this problem:
- Recursive Approach
- Dynamic Programming Approach
- Memoization Approach
We also covered in detail how both of the approaches work and what is the significance of both of them respectively. Discussed their time complexity as well as space complexity along with a proper explanation. Different programmers prefer different languages for coding. So we kept in mind all our readers. That’s why, this article also contains well-explained codes of both the approaches in the three most popular languages which are c++, Java and python along with their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article. Happy Learning! People are also reading:
- Longest subarray with sum as K
- WAP to Count no. of alphabets, digits and spaces present in a file
- Merge Two Sorted Arrays in-place
- Majority Element
- Rod Cutting Problem – Dynamic Programming
- Program to Rotate an Array
- WAP to Print Triangle Using * Character
- Merge Sort for Linked Lists
- Maximum of all Subarrays of size K
- Reverse a Linked List
Leave a Comment on this Post