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, n1, sum) or isSubsetSum( set, n1, sumset[n1]) # 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 polynomialtime approach, this approach is a better one as it solves this problem in a pseudopolynomial time. Here, we are going to initialize a boolean 2D 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 2D 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...j1] // 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 // bottomup 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...j1] // 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 // bottomup 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...j1] // 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 // bottomup 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...j1] # 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 # bottomup fashion. for i in range(1, n + 1): for j in range(1, sum + 1): if j<set[i1]: subset[i][j] = subset[i1][j] if j>= set[i1]: subset[i][j] = (subset[i1][j] or subset[i  1][jset[i1]]) 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: Pseudopolynomial time, which means that the code is running in a time that is polynomial, but unlike the polynomialtime 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 2D 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 abovecomputed 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 abovecomputed 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 wellexplained manner. We have included proper diagrams of trees for a better understanding of the readers. We also learned about what is postorder 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 wellexplained 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 wellexplained 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 inplace
 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