encode_word.cc

void encode_word(string &s) {
    encode_word_helper(s, 0);
}

void encode_word_helper(string &s, int i) {
    if (i == s.size()) {
        cout << reduce(s) << endl;
        return;
    }
    
    char c = s[i];
    encode_word_helper(s, i + 1);
    s[i] = '1';
    encode_word_helper(s, i + 1);
    s[i] = c;
}

string reduce (const string &s) {
    string ret;
    int i = 0;
    while (i < s.size()) {
        if (s[i] == '1') {
            int cnt = 0;
            for (; i < s.size(); i++) {
                if (s[i] == '1') {
                    cnt++;
                } else {
                    break;
                }
            }
            ret += to_string(cnt);
        } else {
            ret.push_back(s[i++]);
        }
    }
    return ret;
}