Program Overview

This C++ program generates all possible combinations of a given set of elements. The program uses a recursive backtracking approach to explore all combinations efficiently.

Program Structure

• Function generateCombinations: This function generates combinations recursively.
• Function printCombinations: This function prints the generated combinations.
• Main Function: Initializes the set and calls the necessary functions to generate and print combinations.

C++ Code

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

using namespace std; /** * Generates all combinations of a set recursively. * * @param set The original set of elements. * @param index The current index in the set. * @param currentCombination The current combination being formed. * @param allCombinations A 2D vector to store all combinations. */ void generateCombinations(const vector& set, int index, vector& currentCombination, vector<vector>& allCombinations) { // Add the current combination to the list of all combinations allCombinations.push_back(currentCombination); // Generate combinations starting from the current index for (int i = index; i < set.size(); i++) { currentCombination.push_back(set[i]); // Include set[i] generateCombinations(set, i + 1, currentCombination, allCombinations); // Recur with next index currentCombination.pop_back(); // Exclude set[i] and backtrack } } /** * Prints all the combinations generated. * * @param combinations The 2D vector containing all combinations. */ void printCombinations(const vector<vector>& combinations) { for (const auto& combination : combinations) { cout << "{ "; for (int num : combination) { cout << num << " "; } cout << "}" << endl; } } /** * Main function to drive the program. */ int main() { vector set = {1, 2, 3}; // Example set vector<vector> allCombinations; vector currentCombination; generateCombinations(set, 0, currentCombination, allCombinations); cout << "All combinations of the set are:" << endl; printCombinations(allCombinations); return 0; }

How It Works

1. The generateCombinations function begins by adding the current combination to the list of all combinations.

2. It then iterates through the elements of the set starting from the specified index, adding each element to the current combination and making a recursive call.

3. After exploring all combinations that include the current element, it backtracks by removing the last element added.

4. The process continues until all combinations have been generated.

Example Output

All combinations of the set are:
{ }
{ 1 }
{ 1 2 }
{ 1 2 3 }
{ 1 3 }
{ 2 }
{ 2 3 }
{ 3 }