CODEWITHSUNDEEP
c++recursion
Rex F
Rex F

Reputation: 85

Recursion - subsets - C++

Thanks @Scotty, @paddy. FYI, the optimal solution is this:

void RecSubsets(string soFar, string rest) {
    if (rest == "") {
        cout << soFar << end;
    }
    else {
      RecSubsets(soFar + rest[0], rest.substr(1));
      RecSubsets(soFar, rest.substr(1));
    }
 }

void CanMakeSum(string set) {
    RecSubsets("", set);
 }

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 string of 'abcd', it'd split into 2 groups (abcd and abc) and then print out the combinations by calling the function recursively. Under this logic, 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

Upvotes: 0

Views: 3392

Answers (2)

paddy
paddy

Reputation: 63471

You want to print the results in post-order rather than pre-order. The other answer is almost correct, but you have dismissed it too readily. It is not doing permutations because there is no reordering of the string.

The correct code to output the data in the order you require is this:

void RecSubsets(string soFar, string rest) {
    for (int i = 0; i < rest.length(); i++) {
        string next = soFar + rest[i];
        string remaining = rest.substr(i+1);
        RecSubsets(next, remaining);
    }
    if( soFar.size() > 0 ) cout << soFar << endl;
}

Output:

abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d
bcd
bc
bd
b
cd
c
d

Upvotes: 0

Scotty
Scotty

Reputation: 2510

It's a good attempt. There are just two small problems:

  1. You should not be "splitting the data into two sets (C(n-1, k-1) & C(n-1, k))". That's what your recursive function is for!

  2. RecSubsets() should always print out soFar. Remove the if (rest == "").

For example:

void RecSubsets(string soFar, string rest) {
    // First print out "a" or wherever we are up to
    // This ensures we correctly get "ab" and "ac" without trailing characters etc
    cout << soFar << end;

    // Now print out the other combinations that begin with soFar
    // This part of your algorithm was already correct :)
    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);
    // Don't call it a second time here
}

Upvotes: 0

Related Questions