Objective

The objective of this program is to generate all subsets of a given set of integers that sum up to a specified target value. This is a common problem in computer science, often used in algorithm design and optimization tasks. By solving this, we can gain insights into subset generation, recursion, and the use of backtracking techniques.

#include 

void findSubsets(int arr[], int n, int index, int currentSum, int targetSum, int subset[], int subsetSize) {
    // Base case: if currentSum equals targetSum, print the subset
    if (currentSum == targetSum) {
        printf("{ ");
        for (int i = 0; i < subsetSize; i++) { printf("%d ", subset[i]); } printf("}\n"); } // If index is out of bounds, return if (index >= n) {
        return;
    }
    
    // Include the current element in the subset
    subset[subsetSize] = arr[index];
    findSubsets(arr, n, index + 1, currentSum + arr[index], targetSum, subset, subsetSize + 1);
    
    // Exclude the current element from the subset
    findSubsets(arr, n, index + 1, currentSum, targetSum, subset, subsetSize);
}

void generateSubsetsWithSum(int arr[], int n, int targetSum) {
    int subset[n]; // Temporary array to store subsets
    findSubsets(arr, n, 0, 0, targetSum, subset, 0);
}

int main() {
    int arr[] = {3, 34, 4, 12, 5, 2};
    int targetSum = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Subsets with sum %d:\n", targetSum);
    generateSubsetsWithSum(arr, n, targetSum);
    
    return 0;
}

Program Structure Explanation

The program consists of several key components:

• findSubsets Function: This recursive function generates all subsets. It takes parameters such as the array, its size, the current index, the current sum of the subset being built, the target sum, the current subset, and the size of that subset.
• generateSubsetsWithSum Function: This function initializes a temporary array to store subsets and calls the recursive function.
• main Function: This is the entry point of the program. It defines the input array and target sum, and calls the function to generate subsets.

How to Run the Program

1. Copy the provided C code into a text editor.
2. Save the file with a .c extension (e.g., subset_sum.c).
3. Open a terminal or command prompt.
4. Navigate to the directory where the file is saved.
5. Compile the program using a C compiler (e.g., gcc subset_sum.c -o subset_sum).
6. Run the compiled program (e.g., ./subset_sum on Unix/Linux or subset_sum.exe on Windows).

Conclusion

This program effectively demonstrates the use of recursion to explore all subsets of a given array and identify those that meet a specific sum condition. It serves as a useful example for understanding combinatorial problems in programming.