The following code is buggy, the goal is to print the powerset of the given stri

Question

The following code is buggy, the goal is to print the powerset of the given string with as few modifications to the exisitng code as possible (it currently only prints out the whole string once), I can't think of how to do this without using a data structure. Any help is appreciated, the code must be executed recursively, and in C++.

#include

#include

using namespace std;

void PrintPowerSet(string a, string b) {

if (a.empty()) {

cout << '{' << b << "}" << endl;

return;

}

b += a[0];

PrintPowerSet(a.substr(1), b);

}

void PrintPowerSet(string a) {

PrintPowerSet(a, "");

}

int main() {

string a = "abcdefg";

PrintPowerSet(a);

return 0;

}

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

// Utility function to split the string using a delim. Refer -
// http://stackoverflow.com/questions/236129/split-a-string-in-c
vector<string> split(const string &s, char delim)
{
vector<string> elems;
stringstream ss(s);
string item;
while (getline(ss, item, delim))
elems.push_back(item);

return elems;
}

// Function to find all subsets of given set. Any repeated
// subset is considered only once in the output
int printPowerSet(int arr[], int n)
{
vector<string> list;

/* Run counter i from 000..0 to 111..1*/
for (int i = 0; i < (int) pow(2, n); i++)
{
string subset = "";

// consider each element in the set
for (int j = 0; j < n; j++)
{
// Check if jth bit in the i is set. If the bit
// is set, we consider jth element from set
if ((i & (1 << j)) != 0)
subset += to_string(arr[j]) + "|";
}

// if subset is encountered for the first time
// If we use set<string>, we can directly insert
if (find(list.begin(), list.end(), subset) == list.end())
list.push_back(subset);
}

// consider every subset
for (string subset : list)
{
// split the subset and print its elements
vector<string> arr = split(subset, '|');
for (string str: arr)
cout << str << " ";
cout << endl;
}
}

// Driver code
int main()
{
string temp = "abcdefg";
char tab2[temp.size()+1];
strcpy(tab2, temp.c_str());
int n =(sizeof(tab2)/sizeof(*tab2)) ;
cout<<n;
printPowerSet(tab2, n);

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.