Problem Statement

Given an array arr of n integers and an integer target, determine if there is a subset of the given array with a sum equal to the given target.

Constrains

1 <= n = 100
1<= arr[i] <= 100
0<= target <= 5*10^3

• 1 ≤ n = 100
  • The number of elements in the array would be atleast 1 and at most 100.
  • This tell how big the input size can be. Since 100 is not very large, you can use algorithms with time complexity up to (n * target) or even O(n^2) without TLE.
• 1 ≤ arr[i] ≤ 100
  • Every individual number in the array must be between 1 and 100, inclusive.
  • You don't need to handle zeroes, negative numbers, or very large values in arr.
• 0 ≤ target ≤ 5000
  • The value you are trying to reach is between 0 and 5000.
  • If your algorithm uses a dp table indexed by the target (e.g., dp[target]), you need to be able to handle sizes up to 5000. That's very large but manageable in most problems.

Examples

Example 1:

Input: arr = [1, 2, 7, 3], target = 6
Output: True

Explanation: There is a subset (1, 2, 3) with sum 6.

Example 2:

Input: arr = [2, 3, 5], target = 6
Output: False

Explanation: There is no subset with sum6.

Different Approaches

1️⃣ Recursive Approach

The idea is to generate all pssible subsets and whenever a single subsets is found whose sum is equal to the given target, simply return true. As, all the subsets needs to generated, recursion can be used to solve this problem.

Steps to form the recursive solution:

• Express the problem in terms of indexes: The array will have an index but there is one more parameter “target”. So, we can say that initially, we need to find(n-1, target) which means that we need to find whether there exists a subset in the array from index 0 to n-1, whose sum is equal to the target.
  • So, f(ind, target) will check whether a subset exists in the array from index 0 to index 'ind' such that the sum of elements is equal to the target.
• Try out all possible choices at a given index: As all the subsets needs to be generated, we will use the pick/non-pick technique. There will be two choices in each function call:
  • Do not include the current element in the subset: First try to find a subset without considering the current index element. For this, make a recursive call to f(ind-1,target).
  • Include the current element in the subset: Now try to find a subset by considering the current index element as part of subset. As the current element(arr[ind]) is included, the remaining target sum will be target - arr[ind]. Therefore, make a function call of f(ind-1,target-arr[ind]).

Note: Consider the current element in the subset only when the current element is less or equal to the target.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
    not pick = f(ind-1, target)
    pick = false
    if(target <= arr[ind]{
        pick = f(ind-1, target - arr[ind])
    }
           
}

• Return (pick || not pick): As we are looking for only one subset whose sum of elements is equal to target, if any of the one among 'pick' or 'not pick' returns true, it means the required subset is found so, return true.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
   not pick = f(ind-1, target)
    pick = false
    if(target <= arr[ind]{
        pick = f(ind-1, target - arr[ind])
    }
    return (pick || not pick)    
}

• Base cases: There will be two base cases.
  • First, when target == 0, it means that the subset is already found from the previous steps, so simply return true.
  • Another, when ind==0, it means we are at the first element, so return arr[ind]==target. If the element is equal to the target it will return true else false.

Code:

Starting from the end.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Recursive function to check if there is a subset with a sum equal to 'target' */
    bool func(int ind, int target, vector<int>& arr) {
        // Step 1: Base Case - If target is 0, a subset sum of 0 is always possible (empty subset)
        if (target == 0)
            return true;

        // Step 2: Base Case - If we are at index 0, we can only check if the first element equals the target
        if (ind == 0)
            return arr[0] == target;

        // Step 3: Option 1 - Try excluding the current element (not taking it into the subset)
        bool notTaken = func(ind - 1, target, arr);

        // Step 4: Option 2 - Try including the current element in the subset (if it doesn't exceed the target)
        bool taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr);

        // Step 5: Return the result: either we take the element or we don't
        return notTaken || taken;
    }

public:
    /* Public function to start the recursion with the given array and target */
    bool isSubsetSum(vector<int>& arr, int target) {
        // Step 6: Call the recursive function starting from the last index and the target
        return func(arr.size() - 1, target, arr);
    }
};

int main() {
    // Step 7: Initialize the array and target
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;

    // Step 8: Create an instance of Solution class
    Solution sol;
    
    // Step 9: Call the function and print the result based on whether a valid subset is found
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}

Starting from the start:

class Solution{   
public:

    /* Recursive function to check if subset sum is possible */
    bool solve(vector<int>& arr, int index, int target){
        
        // Step 1: Base Case 1 - If target becomes 0, subset found
        if (target == 0) {
            return true;
        }

        // Step 2: Base Case 2 - If target goes negative or no elements left, subset not possible
        if (target < 0 || index >= arr.size()) {
            return false;
        }

        // Step 3: Option 1 - Include the current element (if it does not exceed target)
        bool takeIt = false;
        if (arr[index] <= target) {
            takeIt = solve(arr, index + 1, target - arr[index]);
        }

        // Step 4: Option 2 - Exclude the current element
        bool skipIt = solve(arr, index + 1, target);

        // Step 5: Return true if either option gives a valid subset
        return takeIt || skipIt;
    }

    /* Main function to check for subset sum starting from index 0 */
    bool isSubsetSum(vector<int>arr, int target){
        return solve(arr, 0, target);
    }
};

Complexity Analysis:

• Time Complexity: O(2^(N)), where N is the length of the array. As, for each index, there are two possible options.
• Space Complexity: O(N), at maximum the depth of the recursive stack can go up to N.

2️⃣ Memoization

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

• Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.
  • The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.
• While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
• Store the value of subproblem: Whenever, a subproblem is encountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

Code:

Starting from the end

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if there is a subset of arr
    with a sum equal to 'target' using memoization*/
    bool func(int ind, int target, vector<int>& arr, vector<vector<int>>& dp) {
        // Base cases
        if (target == 0)
            return true;

        if (ind == 0)
            return arr[0] == target;
            
        /* If the result for this subproblem has 
        already been computed, return it*/
        if (dp[ind][target] != -1)
            return dp[ind][target];

        // Try not taking the current element into subset
        bool notTaken = func(ind - 1, target, arr, dp);

        /* Try taking the current element into the 
        subset if it doesn't exceed the target*/
        bool taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr, dp);

        /* Store the result in the dp
        array to avoid recomputation*/
        return dp[ind][target] = notTaken || taken;
    }
public:
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    bool isSubsetSum(vector<int>& arr, int target) {
        // Initialize a 2D DP array for memoization
        vector<vector<int>> dp(arr.size(), vector<int>(target + 1, -1));
        
        // Return the result
        return func(arr.size() - 1, target, arr, dp);
    }
};
int main() {
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;

    //Create an instance of Solution class
    Solution sol;
    
    // Call the subsetSumToK function and print the result
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}

Starting from the start

class Solution{   
public:

    /* Recursive function with memoization to check if subset sum is possible */
    bool solve(vector<int>& arr, int index, int target, vector<vector<int>>& dp){
        
        // Step 1: Base Case - If target becomes negative or we go beyond the array bounds, return false
        if (target < 0 || index >= arr.size()) {
            return false;
        }

        // Step 2: Base Case - If target becomes 0, subset found
        if (target == 0) {
            return true;
        }

        // Step 3: Check if the solution for this subproblem has already been computed
        if (dp[index][target] != -1) {
            return dp[index][target];
        }

        // Step 4: Option 1 - Include the current element (if it does not exceed target)
        bool takeIt = false;
        if (arr[index] <= target) {
            takeIt = solve(arr, index + 1, target - arr[index], dp);
        }

        // Step 5: Option 2 - Exclude the current element
        bool skipIt = solve(arr, index + 1, target, dp);

        // Step 6: Store the result in dp array and return the answer
        return dp[index][target] = takeIt || skipIt;
    }

    /* Main function that initiates the recursive function with memoization */
    bool isSubsetSum(vector<int>arr, int target){
        int n = arr.size();
        // Step 7: Create a dp array initialized to -1 (unvisited state)
        vector<vector<int>> dp (n + 1, vector<int>(target + 1, -1));

        // Step 8: Start the recursion with index 0 and the given target
        return solve(arr, 0, target, dp);
    }
};

Complexity Analysis:

• Time Complexity: O(N*target), There are 'N*target' states therefore at max ‘N*target’ new problems will be solved.
• Space Complexity: O(N*target) + O(N), As we are using a recursion stack space(O(N)) and a 2D array ( O(N*target)).

3️⃣ Tabulation

In order to convert a recursive code to tabulation code, here are the steps which we follows:

1. Declare a dp array of size [n][target + 1]:

   1. As there are two changing parameters in the recursive solution, ind and target. The maximum value ind can attain is (n) and including 0 its n, where n is the size of array, for target can have any values between 0 to target. So we need a 2D dp array. Set its type as bool and initialize it as false.

   

2. Setting Base Cases in the Array:

   1. In the recursive code, out base condition was when target == 0, it means the required subset is found, and we returning true, So, we set true in the dp array for every index where target  = 0.

      

   2. 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 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. Please note that it can happen that target arr[0] > target, so we first check it: if(arr[0] ≤ target) then set dp[0][arr[0] = true.

      

3. Iterative Computation Using Loops:
   1. Initialize two nested for loops to traverse the dp array and following the logic discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations.
4. Returning the answer:
   1. At last dp[n-1][target] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.

Code:

It is when we map index =  0 of input array with the index 0 of the dp array.

 #include <bits/stdc++.h>
using namespace std;

// Define the Solution class
class Solution{
private:
    /* Helper function to check if there is a 
       subset of 'arr' with a sum equal to 'target' */
    bool func(int n, int target, vector<int> &arr) {
        
        // Step 1: Initialize DP table
        vector<vector<bool>> dp(n, vector<bool>(target + 1, false));

        // Step 2: Base Case 1 - Sum 0 is always possible (empty subset)
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }

        // Step 3: Base Case 2 - First element alone can make sum arr[0] (if possible)
        if (arr[0] <= target) {
            dp[0][arr[0]] = true;
        }

        // Step 4: Fill the DP table iteratively
        for (int ind = 1; ind < n; ind++) {         // For every index
            for (int i = 1; i <= target; i++) {      // For every target value from 1 to given target

                // Step 5: Option 1 - Not taking current element
                bool notTaken = dp[ind - 1][i];

                // Step 6: Option 2 - Taking current element (if it fits in target)
                bool taken = false;
                if (arr[ind] <= i) {
                    taken = dp[ind - 1][i - arr[ind]];
                }

                // Step 7: Final DP state for (ind, i)
                dp[ind][i] = notTaken || taken;
            }
        }

        // Step 8: Answer is stored at dp[n-1][target]
        return dp[n - 1][target];
    }

public:
    /* Public function to call the helper 'func' */
    int isSubsetSum(vector<int> arr, int target){
        return func(arr.size(), target, arr);
    }
};

int main() {
    // Step 9: Example input array and target
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;

    // Step 10: Create object of Solution class
    Solution sol;
    
    // Step 11: Call the isSubsetSum function and print the result
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}

Below is for n+1 rows, when we map index 0 of the input array with the index 1 of the dp array.

class Solution{   
public:

    /* Helper function to check if a subset sum to target exists */
    bool func(int n, int target, vector<int> &arr) {
        
        // Step 1: Initialize a DP table of size (n+1) x (target+1)
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));

        // Step 2: Base Case 1 - Sum 0 is always possible with any number of elements (empty subset)
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // Step 3: Base Case 2 - With 0 elements, positive sums are not possible
        for (int i = 1; i <= target; i++) {
            dp[0][i] = false;
        }

        // Step 4: Fill the DP table iteratively
        for (int ind = 1; ind <= n; ind++) {          // For every element from 1 to n
            for (int sum = 1; sum <= target; sum++) {  // For every possible sum from 1 to target

                // Step 5: Option 1 - Not taking the current element
                bool notTaken = dp[ind - 1][sum];

                // Step 6: Option 2 - Taking the current element (if its value <= sum)
                bool taken = false;
                if (arr[ind - 1] <= sum) {
                    taken = dp[ind - 1][sum - arr[ind - 1]];
                }

                // Step 7: Update DP state: either we can take or not take to form 'sum'
                dp[ind][sum] = notTaken || taken;
            }
        }

        // Step 8: Final answer stored at dp[n][target]
        return dp[n][target];
    }

public:
    /* Main function to be called with array and target */
    int isSubsetSum(vector<int> arr, int target){
        return func(arr.size(), target, arr);
    }
};

Complexity Analysis:

• Time Complexity:O(N*target), As, here are three nested loops that account for O(N*target) complexity.
• Space Complexity: O(N*target), As a 2D array of size N*target is used.

4️⃣ Space Optimized Approach

To determine if we can space optimize a dynamic programming solution, the primary concept we rely on is whether we only need previous rows or states to compute the current row/state. If we can only access values from the previous state, and there is no need for all the previous states (like the entire 2D DP table), we can reduce the space complexity.

If we observe the relation obtained in the tabulation, dp[ind][target] = dp[ind - 1][target] || dp[ind - 1][target - arr[ind]]. We We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.

Steps to space optimize the tabulation approach:

1. Decalre an array to store the previous row of the DP table. Initialize the first row and first column of the DP table based on the base conditions discussed in tabulation.
2. Now, initiate two nested loops in bottom-up approach. The first loop will run for 'ind' and the second loop will run for the 'target' variable.
3. In order to store the current row of the DP table, initialize a new array 'cur' and fill the first cell to 'true' for base condition.
4. Do the calculations for 'cur' row by performing the pick/non-pick technique used in previous approaches.
5. Now, update the previous row with the current row for the next iteration and at last return the final result stored in the last cell of the previous row(prev[k]).

Code:

class Solution{   
public:

    bool func(int n, int target, vector<int> &arr) {
        
        // Step 1: Initialize DP table
        vector<bool> prev(target + 1, false);
        prev[0] = true;  // Sum 0 is always possible

        // Step 4: Fill the DP table iteratively
        for (int ind = 1; ind <= n; ind++) {  // For every index
            vector<bool> curr(target + 1, false);
            curr[0] = true;  // Again, sum 0 is always possible

            for (int i = 1; i <= target; i++) {  // For every target value from 1 to given target

                // Step 5: Option 1 - Not taking current element
                bool notTaken = prev[i];

                // Step 6: Option 2 - Taking current element (if it fits in target)
                bool taken = false;
                if (arr[ind - 1] <= i) {
                    taken = prev[i - arr[ind - 1]];
                }

                // Step 7: Final DP state for (ind, i)
                curr[i] = notTaken || taken;
            }
            prev = curr;  // Move current row to previous for next iteration
        }

        // Step 8: Answer is stored in prev[target]
        return prev[target];
    }

public:
    /* Public function to call the helper 'func' */
    int isSubsetSum(vector<int> arr, int target){
        return func(arr.size(), target, arr);
    }
};

Complexity Analysis:

• Time Complexity:O(N*target), As, here are three nested loops that account for O(N*target) complexity.
• Space Complexity: O(target), As we are using two external arrays of size ‘target'.