Table of contents

Subset Sum Problem

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

Input/Output Examples

python
Example 1:
Input:
set = [3, 34, 4, 12, 5, 2]
sum = 9
Output: True
Explanation: There is a subset {4, 5} whose sum is 9.

Example 2:
Input:
set = [3, 34, 4, 12, 5, 2]
sum = 30
Output: False
Explanation: There is no subset whose sum is 30.

Approach to find the subset with maximum sum

  1. Dynamic Programming Approach:
    • We create a boolean DP table dp[i][j] where i is the number of elements considered from the set and j is the target sum. dp[i][j] will be True if a subset of the first i elements has a sum equal to j.
    • Initialize dp[0][0] = True because a sum of 0 can be made by selecting no elements.
    • For each element set[i-1]:
      • If the element is not included, the value of dp[i][j] is the same as dp[i-1][j].
      • If the element is included, dp[i][j] = dp[i-1][j - set[i-1]] (if j >= set[i-1]).
  2. Algorithm:
    • Initialize a DP table of size (n+1) x (sum+1) where n is the number of elements in the set and sum is the target sum.
    • The first row of the DP table represents the case where no elements are considered, and the first column represents the case where the target sum is 0.
    • Traverse through each element of the set and fill the DP table based on whether the element is included in the subset or not.
    • The final answer will be in dp[n][sum].
  3. Edge Cases:
    • If the sum is 0, the answer is always True (since the empty subset has a sum of 0).
    • If the set is empty and the sum is non-zero, the answer is False.

C++ Program to find the subset with maximum sum

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to check if there is a subset with the given sum
bool isSubsetSum(vector<int>& set, int sum) {
    int n = set.size();
    // Create a DP table with dimensions (n+1) x (sum+1)
    vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));

    // Initialize the first column (sum = 0) to true
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // Build the DP table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (set[i - 1] > j) {
                dp[i][j] = dp[i - 1][j]; // Exclude the element
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - set[i - 1]]; // Include or exclude the element
            }
        }
    }

    // Return the answer in dp[n][sum]
    return dp[n][sum];
}

int main() {
    vector<int> set = {3, 34, 4, 12, 5, 2};
    int sum = 9;

    if (isSubsetSum(set, sum)) {
        cout << "Found a subset with given sum" << endl;
    } else {
        cout << "No subset with given sum" << endl;
    }

    return 0;
}

Java Program to find the subset with maximum sum

java
public class SubsetSum {

    // Function to check if there is a subset with the given sum
    public static boolean isSubsetSum(int[] set, int sum) {
        int n = set.length;
        // Create a DP table with dimensions (n+1) x (sum+1)
        boolean[][] dp = new boolean[n + 1][sum + 1];

        // Initialize the first column (sum = 0) to true
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // Build the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (set[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j]; // Exclude the element
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - set[i - 1]]; // Include or exclude the element
                }
            }
        }

        // Return the answer in dp[n][sum]
        return dp[n][sum];
    }

    public static void main(String[] args) {
        int[] set = {3, 34, 4, 12, 5, 2};
        int sum = 9;

        if (isSubsetSum(set, sum)) {
            System.out.println("Found a subset with given sum");
        } else {
            System.out.println("No subset with given sum");
        }
    }
}

Java Program to find the subset with maximum sum

java
# Function to check if there is a subset with the given sum
def is_subset_sum(set, sum):
    n = len(set)
    # Create a DP table with dimensions (n+1) x (sum+1)
    dp = [[False for _ in range(sum + 1)] for _ in range(n + 1)]

    # Initialize the first column (sum = 0) to True
    for i in range(n + 1):
        dp[i][0] = True

    # Build the DP table
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if set[i - 1] > j:
                dp[i][j] = dp[i - 1][j]  # Exclude the element
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - set[i - 1]]  # Include or exclude the element

    # Return the answer in dp[n][sum]
    return dp[n][sum]

# Example usage
if __name__ == "__main__":
    set = [3, 34, 4, 12, 5, 2]
    sum = 9
    if is_subset_sum(set, sum):
        print("Found a subset with given sum")
    else:
        print("No subset with given sum")

Time Complexity:

  • O(n * sum): We iterate through all elements of the set and all possible sums from 0 to sum, resulting in a time complexity proportional to n * sum.

Space Complexity:

  • O(n * sum): We use a 2D DP table of size (n + 1) x (sum + 1) to store the results of subproblems.

DSA

Related Articles