Program Overview

This program determines if there exists a subset of a given set of integers that adds up to a specified sum using dynamic programming. This problem is known as the Subset Sum Problem.

Program Structure

• Input: An array of integers and a target sum.
• Dynamic Programming Table: A 2D array to store boolean values indicating whether a subset with a certain sum can be formed with the first i elements.
• Output: A boolean value indicating whether a subset with the given sum exists.

C Program

#include 
#include 

// Function to determine if a subset with a given sum exists
bool isSubsetSum(int set[], int n, int sum) {
    bool dp[n + 1][sum + 1]; // DP table

    // Initialize the table
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
            // If sum is 0, we can always form it with an empty subset
            if (j == 0) {
                dp[i][j] = true;
            }
            // If no items are selected, we cannot form a positive sum
            else if (i == 0) {
                dp[i][j] = false;
            }
            // If the current item is less than or equal to the sum
            else if (set[i - 1] <= j) {
                // Include the current item or exclude it
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - set[i - 1]];
            } else {
                // Exclude the current item
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][sum]; // The result is in the last cell of the table
}

// Main function
int main() {
    int n, sum;

    // Input the number of elements and the target sum
    printf("Enter the number of elements in the set: ");
    scanf("%d", &n);
    
    int set[n];
    printf("Enter the elements of the set:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &set[i]);
    }
    
    printf("Enter the target sum: ");
    scanf("%d", &sum);

    // Determine if a subset with the given sum exists
    if (isSubsetSum(set, n, sum)) {
        printf("A subset with the given sum exists.\n");
    } else {
        printf("No subset with the given sum exists.\n");
    }

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for determining the subset sum and the main function to handle input and output:

• The isSubsetSum function implements the dynamic programming approach:
  • A 2D array dp is created to store boolean values representing whether a subset sum can be achieved with the first i elements.
  • The function initializes the table based on the rules: if the sum is 0, it can always be achieved with an empty subset. If no items are selected, no positive sum can be achieved.
  • It then iterates through each element and possible sum, deciding whether to include or exclude the current item based on whether it can contribute to forming the sum.
• The main function handles user input:
  • The user is prompted to enter the number of elements in the set and the target sum.
  • It calculates whether a subset with the given sum exists by calling the isSubsetSum function and displays the result.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the number of elements and the elements of the set.
3. Input the target sum.
4. The program will output whether a subset with the given sum exists.