Program Explanation

This C++ program generates all subsets of a given array that sum to a specified target.
The approach used is recursive backtracking, where we explore each element in the array
and decide whether to include it in the current subset or not.

Program Structure

• Main Function: Initializes the input array, target sum, and calls the recursive function.
• Subset Sum Function: The recursive function that constructs subsets and checks their sums.
• Display Function: Outputs the valid subsets that meet the target sum.

Code

#include <iostream> 
#include <vector> 
#include <string>

using namespace std; // Function to find all subsets with a given sum void findSubsetsWithSum(const vector& arr, int target, vector& subset, int index) { // Base case: If we reach the end of the array if (index == arr.size()) { // Check if the current subset sums to the target int sum = 0; for (int num : subset) { sum += num; } if (sum == target) { // Print the valid subset cout << "{ "; for (int num : subset) { cout << num << " "; } cout << "}" << endl; } return; } // Include the current element subset.push_back(arr[index]); findSubsetsWithSum(arr, target, subset, index + 1); // Exclude the current element subset.pop_back(); findSubsetsWithSum(arr, target, subset, index + 1); } // Main function int main() { vector arr = {2, 4, 6, 10}; // Example array int target = 16; // Target sum vector subset; // To store the current subset cout << "Subsets with sum " << target << " are:" << endl; findSubsetsWithSum(arr, target, subset, 0); return 0; } 

Explanation of the Code

1. Includes and Namespace: We include the necessary headers and use the std namespace.
2. Function findSubsetsWithSum:
   • This function takes the array, target sum, a reference to the current subset, and the current index as parameters.
   • It checks if we have processed all elements of the array. If so, it sums the current subset and checks if it equals the target. If it does, the subset is printed.
   • The function uses recursion to explore two possibilities for each element: including it in the current subset or excluding it.
3. Main Function:
   • Initializes an example array and a target sum.
   • Calls the recursive function to find and display all valid subsets.

How to Compile and Run

1. Save the code to a file named subset_sum.cpp.
2. Open a terminal and navigate to the directory containing the file.
3. Compile the program using the command: g++ subset_sum.cpp -o subset_sum.
4. Run the program with: ./subset_sum.

Conclusion

This program effectively demonstrates how to use recursion to explore subsets of an array
and check their sums. You can modify the input array and target sum to test different scenarios.