Count Subsets with Sum K (DP – 17)

A Greedy Solution doesn’t make sense because we are not looking to optimize anything. We can rather try to generate all subsequences using recursion and whenever we get a single subsequence whose sum is equal to the given target, we can count it.

Note: Readers are highly advised to watch this video “Recursion on Subsequences” to understand how we generate subsequences using recursion.

Steps to form the recursive solution:

We will first form the recursive solution by the three points mentioned in Dynamic Programming Introduction.

Step 1: Express the problem in terms of indexes.

The array will have an index but there is one more parameter “target”. We are given the initial problem to find whether there exists in the whole array a subsequence whose sum is equal to the target.

So, we can say that initially, we need to find(n-1, target) which means that we are counting the number of subsequences in the array from index 0 to n-1, whose sum is equal to the target. Similarly, we can generalize it for any index ind as follows:

Base Cases:

If target == 0, it means that we have already found the subsequence from the previous steps, so we can return 1.
If ind==0, it means we are at the first element, so we need to return arr[ind]==target. If the element is equal to the target we return 1 else we return 0.

Step 2: Try out all possible choices at a given index.

We need to generate all the subsequences. We will use the pick/non-pick technique as discussed in this video “Recursion on Subsequences”.

We have two choices:

Exclude the current element in the subsequence: We first try to find a subsequence without considering the current index element. For this, we will make a recursive call to f(ind-1,target).
Include the current element in the subsequence: We will try to find a subsequence by considering the current index as element as part of subsequence. As we have included arr[ind], the updated target which we need to find in the rest if the array will be target – arr[ind]. Therefore, we will call f(ind-1,target-arr[ind]).

Note: We will consider the current element in the subsequence only when the current element is less than or equal to the target.

Step 3: Return sum of taken and notTaken

As we have to return the total count of subsets with the target sum, we will return the sum of taken and notTaken from our recursive call.

The final pseudocode after steps 1, 2, and 3:

Steps to memoize a recursive solution:

If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:

Create a dp array of size [n][k+1]. The size of the input array is ‘n’, so the index will always lie between ‘0’ and ‘n-1’. The target can take any value between ‘0’ and ‘k’. Therefore we take the dp array as dp[n][k+1]
We initialize the dp array to -1.
Whenever we want to find the answer of particular parameters (say f(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.
If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[ind][target] to the solution we get.

Code


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

// Function to count the number of subsets with a given sum
int findWaysUtil(int ind, int target, vector<int>& arr, vector<vector<int>>& dp) {
    // Base case: If the target sum is 0, we found a valid subset
    if (target == 0)
        return 1;

    // Base case: If we have considered all elements and the target is still not 0, return 0
    if (ind == 0)
        return (arr[0] == target) ? 1 : 0;

    // If the result for this state is already calculated, return it
    if (dp[ind][target] != -1)
        return dp[ind][target];

    // Recursive cases
    // 1. Exclude the current element
    int notTaken = findWaysUtil(ind - 1, target, arr, dp);

    // 2. Include the current element if it doesn't exceed the target
    int taken = 0;
    if (arr[ind] <= target)
        taken = findWaysUtil(ind - 1, target - arr[ind], arr, dp);

    // Store the result in the DP table and return
    return dp[ind][target] = notTaken + taken;
}

// Function to count the number of subsets with a given sum
int findWays(vector<int>& num, int k) {
    int n = num.size();
    vector<vector<int>> dp(n, vector<int>(k + 1, -1));
    return findWaysUtil(n - 1, k, num, dp);
}

int main() {
    vector<int> arr = {1, 2, 2, 3};
    int k = 3;

    cout << "The number of subsets found are " << findWays(arr, k);

    return 0;
}


import java.util.*;

class TUF {
    // Helper function to find the number of ways to achieve a target sum
    static int findWaysUtil(int ind, int target, int[] arr, int[][] dp) {
        if (target == 0)
            return 1;

        if (ind == 0)
            return arr[0] == target ? 1 : 0;

        if (dp[ind][target] != -1)
            return dp[ind][target];

        // Calculate the number of ways when the current element is not taken
        int notTaken = findWaysUtil(ind - 1, target, arr, dp);

        // Calculate the number of ways when the current element is taken
        int taken = 0;
        if (arr[ind] <= target)
            taken = findWaysUtil(ind - 1, target - arr[ind], arr, dp);

        // Store and return the result for the current state
        return dp[ind][target] = notTaken + taken;
    }

    // Main function to find the number of ways to form subsets with a target sum
    static int findWays(int[] num, int k) {
        int n = num.length;
        int dp[][] = new int[n][k + 1];

        for (int row[] : dp)
            Arrays.fill(row, -1);

        return findWaysUtil(n - 1, k, num, dp);
    }

    public static void main(String args[]) {
        int arr[] = {1, 2, 2, 3};
        int k = 3;

        // Calculate and print the number of subsets that sum up to k
        System.out.println("The number of subsets found are " + findWays(arr, k));
    }
}


def findWays(num, k):
    n = len(num)
    
    # Initialize a 2D DP array to store the count of subsets for different targets.
    dp = [[0] * (k + 1) for _ in range(n)]
    
    # Base case: There is always one way to make a subset with a target sum of 0 (empty subset).
    for i in range(n):
        dp[i][0] = 1
    
    # Handle the base case for the first element in the array.
    if num[0] <= k:
        dp[0][num[0]] = 1

    # Iterate through the elements in the array.
    for ind in range(1, n):
        for target in range(1, k + 1):
            # If the current element is not taken, the count is the same as the previous row.
            notTaken = dp[ind - 1][target]
            
            # If the current element is taken, subtract its value from the target and check the previous row.
            taken = 0
            if num[ind] <= target:
                taken = dp[ind - 1][target - num[ind]]
            
            # Update the DP array with the total count of ways (taken + notTaken).
            dp[ind][target] = notTaken + taken

    # The result is stored in the bottom-right cell of the DP array.
    return dp[n - 1][k]

def main():
    arr = [1, 2, 2, 3]
    k = 3
    
    # Find and print the number of subsets that can be formed with a sum of 'k'.
    print("The number of subsets found are", findWays(arr, k))

if __name__ == "__main__":
    main()


function findWaysUtil(ind, target, arr, dp) {
  if (target === 0)
    return 1;

  if (ind === 0)
    return arr[0] === target ? 1 : 0;

  if (dp[ind][target] !== -1)
    return dp[ind][target];

  const notTaken = findWaysUtil(ind - 1, target, arr, dp);

  let taken = 0;
  if (arr[ind] <= target)
    taken = findWaysUtil(ind - 1, target - arr[ind], arr, dp);

  return dp[ind][target] = notTaken + taken;
}

// Function to find the number of subsets with the given sum 'k'
function findWays(num, k) {
  const n = num.length;
  const dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(k + 1).fill(-1);
  }

  return findWaysUtil(n - 1, k, num, dp);
}

// Main function
function main() {
  const arr = [1, 2, 2, 3];
  const k = 3;

  console.log("The number of subsets found are: " + findWays(arr, k));
}

// Run the main function
main();

Output: The number of subsets found are 3

Complexity Analysis

Time Complexity: O(N*K)

Reason: There are N*K states therefore at max ‘N*K’ new problems will be solved.

Space Complexity: O(N*K) + O(N)

Reason: We are using a recursion stack space(O(N)) and a 2D array ( O(N*K)).

Tabulation Approach

Algorithm / Intuition

To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can initialize it as 0.

First, we need to initialize the base conditions of the recursive solution.

If target == 0, ind can take any value from 0 to n-1, therefore we need to set the value of the first column as 1.

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]] =1, (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 arr[0]>target, so we first check it: if(arr[0]<=target) then set dp[0][arr[0]] = 1.

After that, we will set our nested for loops to traverse the dp array, and following the logic discussed in the recursive approach, we will set the value of each cell. Instead of recursive calls, we will use the dp array itself.
At last, we will return dp[n-1][k] as our answer.

Code


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

// Function to count the number of subsets with a given sum
int findWays(vector<int>& num, int k) {
    int n = num.size();

    // Create a 2D DP table with dimensions n x k+1, initialized with zeros
    vector<vector<int>> dp(n, vector<int>(k + 1, 0));

    // Base case: If the target sum is 0, there is one valid subset (the empty subset)
    for (int i = 0; i < n; i++) {
        dp[i][0] = 1;
    }

    // Initialize the first row based on the first element of the array
    if (num[0] <= k) {
        dp[0][num[0]] = 1;
    }

    // Fill in the DP table using a bottom-up approach
    for (int ind = 1; ind < n; ind++) {
        for (int target = 1; target <= k; target++) {
            // Exclude the current element
            int notTaken = dp[ind - 1][target];

            // Include the current element if it doesn't exceed the target
            int taken = 0;
            if (num[ind] <= target) {
                taken = dp[ind - 1][target - num[ind]];
            }

            // Update the DP table
            dp[ind][target] = notTaken + taken;
        }
    }

    // The final result is in the last cell of the DP table
    return dp[n - 1][k];
}

int main() {
    vector<int> arr = {1, 2, 2, 3};
    int k = 3;

    cout << "The number of subsets found are " << findWays(arr, k);

    return 0;
}


import java.util.*;

class TUF {
    // Function to find the number of subsets with a given target sum
    static int findWays(int[] num, int k) {
        int n = num.length;

        // Create a 2D DP array to store the number of ways to achieve each target sum
        int[][] dp = new int[n][k + 1];

        // Initialize the first row of the DP array
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }

        // Initialize the first column of the DP array
        if (num[0] <= k) {
            dp[0][num[0]] = 1;
        }

        // Fill in the DP array using bottom-up dynamic programming
        for (int ind = 1; ind < n; ind++) {
            for (int target = 1; target <= k; target++) {
                // Calculate the number of ways when the current element is not taken
                int notTaken = dp[ind - 1][target];

                // Calculate the number of ways when the current element is taken
                int taken = 0;
                if (num[ind] <= target) {
                    taken = dp[ind - 1][target - num[ind]];
                }

                // Update the DP array for the current element and target sum
                dp[ind][target] = notTaken + taken;
            }
        }

        // The result is stored in the last cell of the DP array
        return dp[n - 1][k];
    }

    public static void main(String args[]) {
        int arr[] = {1, 2, 2, 3};
        int k = 3;

        // Calculate and print the number of subsets that sum up to k
        System.out.println("The number of subsets found are " + findWays(arr, k));
    }
}


def findWays(num, k):
    n = len(num)
    
    # Initialize a 2D DP array to store the count of subsets for different targets.
    dp = [[0] * (k + 1) for _ in range(n)]
    
    # Base case: There is always one way to make a subset with a target sum of 0 (empty subset).
    for i in range(n):
        dp[i][0] = 1
    
    # Handle the base case for the first element in the array.
    if num[0] <= k:
        dp[0][num[0]] = 1

    # Iterate through the elements in the array.
    for ind in range(1, n):
        for target in range(1, k + 1):
            # If the current element is not taken, the count is the same as the previous row.
            notTaken = dp[ind - 1][target]
            
            # If the current element is taken, subtract its value from the target and check the previous row.
            taken = 0
            if num[ind] <= target:
                taken = dp[ind - 1][target - num[ind]]
            
            # Update the DP array with the total count of ways (taken + notTaken).
            dp[ind][target] = notTaken + taken

    # The result is stored in the bottom-right cell of the DP array.
    return dp[n - 1][k]

def main():
    arr = [1, 2, 2, 3]
    k = 3
    
    # Find and print the number of subsets that can be formed with a sum of 'k'.
    print("The number of subsets found are", findWays(arr, k))

if __name__ == "__main__":
    main()


function findWays(num, k) {
  const n = num.length;

  // Create a 2D array 'dp' for dynamic programming
  const dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(k + 1).fill(0);
  }

  // Initialize the first row of 'dp' to 1 (only one way to get a sum of 0)
  for (let i = 0; i < n; i++) {
    dp[i][0] = 1;
  }

  // Initialize the first column of 'dp' based on the first element of 'num'
  if (num[0] <= k) {
    dp[0][num[0]] = 1;
  }

  // Fill the 'dp' array using bottom-up dynamic programming
  for (let ind = 1; ind < n; ind++) {
    for (let target = 1; target <= k; target++) {
      const notTaken = dp[ind - 1][target];

      let taken = 0;
      if (num[ind] <= target) {
        taken = dp[ind - 1][target - num[ind]];
      }

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

  return dp[n - 1][k];
}

// Main function
function main() {
  const arr = [1, 2, 2, 3];
  const k = 3;

  console.log("The number of subsets found are: " + findWays(arr, k));
}

// Run the main function
main();

Output: The number of subsets found are 3

Complexity Analysis

Time Complexity: O(N*K)

Reason: There are two nested loops

Space Complexity: O(N*K)

Reason: We are using an external array of size ‘N*K’. Stack Space is eliminated.

Space Optimization Approach

Algorithm / Intuition

If we closely look the relation,

dp[ind][target] = dp[ind-1][target] + dp[ind-1][target-arr[ind]]

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.

Note: Whenever we create a new row ( say cur), we need to explicitly set its first element is true according to our base condition.

Code


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

// Function to count the number of subsets with a given sum
int findWays(vector<int>& num, int k) {
    int n = num.size();

    // Initialize a vector 'prev' to represent the previous row of the DP table
    vector<int> prev(k + 1, 0);

    // Base case: If the target sum is 0, there is one valid subset (the empty subset)
    prev[0] = 1;

    // Initialize the first row based on the first element of the array
    if (num[0] <= k) {
        prev[num[0]] = 1;
    }

    // Fill in the DP table using a bottom-up approach
    for (int ind = 1; ind < n; ind++) {
        // Create a vector 'cur' to represent the current row of the DP table
        vector<int> cur(k + 1, 0);

        cur[0] = 1;

        for (int target = 1; target <= k; target++) {
            // Exclude the current element
            int notTaken = prev[target];

            // Include the current element if it doesn't exceed the target
            int taken = 0;
            if (num[ind] <= target) {
                taken = prev[target - num[ind]];
            }

            // Update the current row of the DP table
            cur[target] = notTaken + taken;
        }

        // Set 'cur' as 'prev' for the next iteration
        prev = cur;
    }

    // The final result is in the last cell of the 'prev' vector
    return prev[k];
}

int main() {
    vector<int> arr = {1, 2, 2, 3};
    int k = 3;

    cout << "The number of subsets found are " << findWays(arr, k);

    return 0;
}


import java.util.*;

class TUF {
    // Function to find the number of subsets with a given target sum
    static int findWays(int[] num, int k) {
        int n = num.length;

        // Create an array to store the number of ways to achieve each target sum
        int[] prev = new int[k + 1];

        // Initialize the first element of the array
        prev[0] = 1;

        // Initialize the array for the first column
        if (num[0] <= k) {
            prev[num[0]] = 1;
        }

        // Fill in the array using bottom-up dynamic programming
        for (int ind = 1; ind < n; ind++) {
            // Create an array to store the number of ways for the current element
            int[] cur = new int[k + 1];

            // Initialize the first element of the current array
            cur[0] = 1;

            for (int target = 1; target <= k; target++) {
                // Calculate the number of ways when the current element is not taken
                int notTaken = prev[target];

                // Calculate the number of ways when the current element is taken
                int taken = 0;
                if (num[ind] <= target) {
                    taken = prev[target - num[ind]];
                }

                // Update the current array for the current element and target sum
                cur[target] = notTaken + taken;
            }

            // Update the previous array with the current array for the next iteration
            prev = cur;
        }

        // The result is stored in the last element of the array
        return prev[k];
    }

    public static void main(String args[]) {
        int arr[] = {1, 2, 2, 3};
        int k = 3;

        // Calculate and print the number of subsets that sum up to k
        System.out.println("The number of subsets found are " + findWays(arr, k));
    }
}


def findWays(num, k):
    n = len(num)

    # Initialize a list 'prev' to store the count of subsets for different targets.
    prev = [0 for i in range(k + 1)]
    
    # Base case: There is always one way to make a subset with a target sum of 0 (empty subset).
    prev[0] = 1
    
    # Handle the base case for the first element in the array.
    if num[0] <= k:
        prev[num[0]] = 1
    
    # Iterate through the elements in the array.
    for ind in range(1, n):
        # Initialize a new list 'cur' to store the count for the current row.
        cur = [0 for i in range(k + 1)]
        cur[0] = 1
        
        for target in range(1, k + 1):
            # If the current element is not taken, the count is the same as the previous row.
            notTaken = prev[target]
    
            # If the current element is taken, subtract its value from the target and check the previous row.
            taken = 0
            if num[ind] <= target:
                taken = prev[target - num[ind]]
        
            # Update the 'cur' list with the total count of ways (taken + notTaken).
            cur[target] = notTaken + taken
        
        # Update 'prev' to 'cur' for the next iteration.
        prev = cur
    
    # The result is stored in 'prev[k]', indicating the count of subsets that can be formed with a sum of 'k'.
    return prev[k]

def main():
    arr = [1, 2, 2, 3]
    k = 3
    
    # Find and print the number of subsets that can be formed with a sum of 'k'.
    print("The number of subsets found are", findWays(arr, k))

if __name__ == "__main__":
    main()


function findWays(num, k) {
  const n = num.length;

  // Initialize the 'prev' array for dynamic programming
  const prev = new Array(k + 1).fill(0);
  prev[0] = 1;

  // Initialize the first column of 'prev' based on the first element of 'num'
  if (num[0] <= k) {
    prev[num[0]] = 1;
  }

  // Fill the 'prev' array using bottom-up dynamic programming
  for (let ind = 1; ind < n; ind++) {
    const cur = new Array(k + 1).fill(0);
    cur[0] = 1;
    for (let target = 1; target <= k; target++) {
      const notTaken = prev[target];

      let taken = 0;
      if (num[ind] <= target) {
        taken = prev[target - num[ind]];
      }

      cur[target] = notTaken + taken;
    }

    // Update 'prev' array with 'cur' for the next iteration
    for (let i = 0; i < prev.length; i++) {
      prev[i] = cur[i];
    }
  }

  return prev[k];
}

// Main function
function main() {
  const arr = [1, 2, 2, 3];
  const k = 3;

  console.log("The number of subsets found are: " + findWays(arr, k));
}

// Run the main function
main();

Output:The number of subsets found are 3

Complexity Analysis

Time Complexity: O(N*K)

Reason: There are two nested loops

Space Complexity: O(K)

Reason: We are using an external array of size ‘K+1’ to store only one row.

Video Explanation

Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article