DAY 15 - Subset Sum Problem

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-15.

DAY 15 Problem: Subset Sum Problem

Given an array of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Example:

Input:
N = 6
arr[] = {3, 34, 4, 12, 5, 2}
sum = 9
Output: 1
Explanation: Here there exists a subset with
sum = 9, 4+3+2 = 9.

Intuition:
The question is pretty direct. We need to see if it is possible to make the required sum with a subset of a given array.
They do not need to be in a consequent order.
One thing I like to do is not think of a better solution even if I can right away but start from the basics. This helps even when you are not understanding a question, especially then.
Let's start from the basic. We can't see any tricks here or there.
Let's try finding all subsets and see if it's possible. Let's form a recurrence relation.

Approach: Recursion

• Base Case establishment: Start from the last index.
• If we have reached our required sum/target, we return true.
• If we have reached the end of our iteration in a recursive way, just see if the last index leads to our target.
• Now that we have established base cases, let's form the recursive relation.(Observe what's changing and what we need at every step).
• We need an index, our target and the array of values.
• Two Options: Take the element in subset or not.
• Not Taken: We just decrement the index.
• Taken: First we need to see if target >= arr[index]. Then if it is: We decrement the index and update target.
• return taken || notTaken.

Code:

bool subsetHelper(int index, int target, vector<int>& arr){
        if(target == 0)
        return true;
        if(index == 0)
        {
            return arr[index] == target;
        }
        bool notTaken = subsetHelper(index-1,target,arr);
        bool taken = false;
        if(target >= arr[index])
        {
        taken = subsetHelper(index-1,target-arr[index],arr);
        }

        return taken || notTaken;
    }

Complexity Analysis:

Time Complexity: O(2^(N))
Space Complexity: O(N-1). Recursion Stack Space.

We need to reduce it's time complexity as it's exponential right now and might fail in extreme test cases.

Approach: Recursion + Memoization

• Initialize a DP vector of vector of type int of the size of index and target with value -1.
• That's because at max we will have to go for index values and target times.
• Whenever we want to find the answer of particular parameters (say subsetHelperMemo(ind,target)), we first check whether the answer is already calculated using the dp array(i.e dp[ind][target]!= -1 ). If yes, simply return the value from the dp array.
• We set every value that we return as it's dp[index][target] as return to store it.

Code:

bool subsetHelperMemo(int index, int target, vector<int>& arr,vector<vector<int>>& dp){
        if(target == 0)
        return true;
        if(index == 0)
        {
            return arr[index] == target;
        }
        if(dp[index][target] != -1)
        {
            return dp[index][target];
        }
        bool notTaken = subsetHelperMemo(index-1,target,arr,dp);
        bool taken = false;
        if(target >= arr[index])
        {
        taken = subsetHelperMemo(index-1,target-arr[index],arr,dp);
        }

        return dp[index][target] = taken || notTaken;
    }

Complexity Analysis:

Time Complexity: O(N*K)
Space Complexity: O(N) + O(N*K). Recursion Stack Space.

We can eliminate the extra recursive stack space using tabulation method.

Approach: Recurrence Tabulation

• To convert a recursive solution into tabulation one, Our approach doesn't change , we simply change the way we store dp values.
• Initialize a Boolean vector> dp of same size as done before and initialize as false.
• If our target is matched/reduced to 0. It can take any values from the any of starting index. Hence we initialize all of them as true.
• The first row dp[0][] indicates that only the first element of the array is considered, therefore for the target value equal to arr[0], only one cell with that target will be true, so explicitly set dp[0][arr[0]] =true, (dp[0][arr[0]] means that we are considering the first element of the array with the target equal to the first element itself). It can happen that arr[0]>target, so we first check if(arr[0]<=target) then set dp[0][arr[0]] = true.
• We then traverse two for loops and follow the condition formed to update values in DP as per our condition.
• At last we will return dp[n-1][k] as our answer.

Code:

bool isSubsetSum(vector<int>arr, int sum){
        int n = arr.size();
        vector<vector<bool>> dp(n, vector<bool> (sum, false));
        //tabulation approach
        for(int i=0; i<n; i++){
            dp[i][0] = true;
        }

        if(arr[0]<=sum)
            dp[0][arr[0]] = true;

        for(int ind = 1; ind<n; ind++){
            for(int target= 1; target<=sum; target++){

                bool notTaken = dp[ind-1][target];

                bool taken = false;
                    if(arr[ind]<=target)
                        taken = dp[ind-1][target-arr[ind]];

                dp[ind][target]= notTaken||taken;
            }
        }

        return dp[n-1][sum];


    }

Complexity Analysis:

Time Complexity: O(N*K)
Space Complexity: O(N*K). Recursion Stack Space.

We can further reduce down the space complexity to constant space here. Because the relation only depends on the previous value rather than the full DP vector.

I'll be updating this with the optimized space complexity soon.

Thanks for reading. Feedback is highly appreciated.