I'm writing a simple program to calculate all possible combinations in a set by splitting the data into 2 sets (C(n-1, k-1) & C(n-1, k)) and calling the function recursively. Below is what I've written:

void RecSubsets(string soFar, string rest) {

if (rest == "") {

cout << soFar << end;

}

else {

for (int i = 0; i < rest.length(); i++) {

string next = soFar + rest[i];

string remaining = rest.substr(i+1);

RecSubsets(next, remaining);

}

}

}

void CanMakeSum(string set) {

RecSubsets("", set);

RecSubsets("", set.substr(1));

}

int main() {

string set = "abcd";

CanMakeSum(set);

return 0;

}

So for an input of 'abcd', it'd split the string into 2 groups (abcd, abc) and then print out the possible combinations by calling the function recursively. Using this algorithm, the output ought to be: abcd, abc, abd, ab, acd, ac, ad, a...

However, using the program above, the output is abcd, abd, acd, ad... I understand conceptually what I'm trying to achieve, but am having difficulty translating it into codes. Can someone pls point out where I'm going wrong? Thanks

void RecSubsets(string soFar, string rest) {

if (rest == "") {

cout << soFar << end;

}

else {

for (int i = 0; i < rest.length(); i++) {

string next = soFar + rest[i];

string remaining = rest.substr(i+1);

RecSubsets(next, remaining);

}

}

}

void CanMakeSum(string set) {

RecSubsets("", set);

RecSubsets("", set.substr(1));

}

int main() {

string set = "abcd";

CanMakeSum(set);

return 0;

}

So for an input of 'abcd', it'd split the string into 2 groups (abcd, abc) and then print out the possible combinations by calling the function recursively. Using this algorithm, the output ought to be: abcd, abc, abd, ab, acd, ac, ad, a...

However, using the program above, the output is abcd, abd, acd, ad... I understand conceptually what I'm trying to achieve, but am having difficulty translating it into codes. Can someone pls point out where I'm going wrong? Thanks

There's an algorithm out there that can be used to create all subsets of any set actually. I think it's called the next subset algorithm. CS people can be pretty creative with their names.

Topic archived. No new replies allowed.