Combinations of string

Create a set containing the combination of all non-empty sub-strings.  Eg:  combination of string "abc" is {a, ab, abc, bc, b, c}
/*
 * StringCombinations.cpp
 *
 *  Created on: Apr 18, 2012
 *      Author: Kiran Hegde
 */

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

using namespace std;

void combine(string prefix, string rest, vector<string> &output) {
    if (prefix.size() > 0)
        output.push_back(prefix);
    for (unsigned int  i=0; i<rest.size(); i++) {
        combine(prefix + rest[i], rest.substr(i+1), output);
    }
}

/**
 * Test the function
 */
int main() {
    string input("abcd");
    vector<string> combs;
    combine("", input, combs);
    cout << "Combinations: " << endl;
    for (unsigned int i=0; i<combs.size(); i++) {
        cout << combs[i] << endl;
    }
}
Comments