Subset Sum Problem

Posted in

Subset Sum Problem
vinaykhatri

Vinay Khatri
Last updated on May 22, 2024

    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:

    1. Either, we can take the current integer in the subset. Then use recursion for the other elements that remained in the subset.
    2. 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

    1. Take a set as input.
    2. Check recursively. If the set is equal to NULL, return False, as there is no element in the set.
    3. If it is not equal to NULL, traverse the set recursively for the last element.
    4. Ignore the element if it is greater than the given sum integer.
    5. If not, check if
      1. We can get the sum by including the last element.
      2. We can get the sum by excluding the last element.
    6. Include the last element and check for the subset in the set whose sum is equal to the given sum integer.
    7. If found, return True.
    8. If not, exclude the last element and again check in the set for the subset whose sum is equal to the given integer.
    9. 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

    1. Create a 2-D set where i is the index of the set elements and j is the sum value.
    2. Return True if there exists a subset with a sum equal to i
    3. If the sum is equal to 0, return True.
    4. Return False if the set is empty.
    5. Check if the current element has a value greater than the current sum integer, we will consider the element for the previous elements.
    6. 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

    1. Create a 2-D array globally.
    2. Return False if the set is empty, or the sum becomes negative.
    3. 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.
    4. Creating a key for a map having unique value using the elements of the input.
    5. Store the result of the problem if it is encountered for the first time.
      1. Computing the result including the element at the last index.
      2. Computing the result excluding the element at the last index.
    6. 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:

    Leave a Comment on this Post

    0 Comments