Breaking a string into a given set of words

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

using namespace std;

bool Check (string str, set<string>& wordDict) {

    cout << "String : [" << str << "]" << endl;

    int sz = str.size();
    if (sz == 0) {
        cout << "Matching found. Returning true" << endl;
        return true;
    }

    for (const auto& word : wordDict) {

        cout << "Trying to match : " << word << " with " << str << endl;
        int word_length = word.size();

        if (word_length > sz) {
            continue;
        } else if (str.substr(0, word_length) == word) {
            cout << "Matched string : " << str.substr(0, word_length) << endl;
            if (Check (str.substr(word_length), wordDict)) {
                return true;
            }
        }
    }

    return false;
}

bool wordBreak (string str, vector<string>& wordDict) {
    set<string> setDict(wordDict.begin(), wordDict.end());
    return Check(str, setDict);
}

int main() {

    string str_a("abcd");
    vector<string> vec_a = {"a", "abc", "b", "cd"};

    cout << "===========================" << endl;
    if (wordBreak(str_a, vec_a)) {
        cout << "Matched" << endl;
    } else {
        cout << "No match found" << endl;
    }
    cout << "===========================" << endl;

    string str_b("algotreego");
    vector<string> vec_b = {"tree", "go", "al"};

    if (wordBreak(str_b, vec_b)) {
        cout << "Matched" << endl;
    } else {
        cout << "No match found" << endl;
    }
    cout << "===========================" << endl;

    string str_c("sunnylion");
    vector<string> vec_c = {"hot", "cups", "sunny", "lio", "nn"};

    if (wordBreak(str_c, vec_c)) {
        cout << "Matched" << endl;
    } else {
        cout << "No match found" << endl;
    }

    return 0;
}

===========================
String : [abcd]
Trying to match : a with abcd
Matched string : a
String : [bcd]
Trying to match : a with bcd
Trying to match : abc with bcd
Trying to match : b with bcd
Matched string : b
String : [cd]
Trying to match : a with cd
Trying to match : abc with cd
Trying to match : b with cd
Trying to match : cd with cd
Matched string : cd
String : []
Matching found. Returning true
Matched
===========================
String : [algotreego]
Trying to match : al with algotreego
Matched string : al
String : [gotreego]
Trying to match : al with gotreego
Trying to match : go with gotreego
Matched string : go
String : [treego]
Trying to match : al with treego
Trying to match : go with treego
Trying to match : tree with treego
Matched string : tree
String : [go]
Trying to match : al with go
Trying to match : go with go
Matched string : go
String : []
Matching found. Returning true
Matched
===========================
String : [sunnylion]
Trying to match : cups with sunnylion
Trying to match : hot with sunnylion
Trying to match : lio with sunnylion
Trying to match : nn with sunnylion
Trying to match : sunny with sunnylion
Matched string : sunny
String : [lion]
Trying to match : cups with lion
Trying to match : hot with lion
Trying to match : lio with lion
Matched string : lio
String : [n]
Trying to match : cups with n
Trying to match : hot with n
Trying to match : lio with n
Trying to match : nn with n
Trying to match : sunny with n
Trying to match : nn with lion
Trying to match : sunny with lion
No match found

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

using namespace std;

void Check (string str, set<string>& wordDict, vector<string>& vec_str, vector<string>& result) {

    int sz = str.size();

    // Size of the remaining string is 0. i.e it has been split into dictionary words
    if (sz == 0) {
        string sentence("");
        for (const auto& str : vec_str) {
             sentence.append(str);
             sentence.append(" ");
        }
        sentence.erase(sentence.size()-1, 1); // Remove the last space
        result.push_back(sentence);
        return;
    }

    for (const auto& word : wordDict) {

        int word_length = word.size();

        if (word_length > sz) {
            continue;
        } else if (str.substr(0, word_length) == word) {
            vec_str.push_back(str.substr(0, word_length));
            Check (str.substr(word_length), wordDict, vec_str, result);
            vec_str.pop_back();
        }
    }
}

vector<string> WordBreak (string str, vector<string>& wordDict) {

    vector<string> vec_string; // Stores all matching words.
    vector<string> result; // Stores all possible sentences containing the dictionary words.
    set<string> setDict(wordDict.begin(), wordDict.end());

    Check(str, setDict, vec_string, result);

    return result;
}

int main() {

    string str_a("abcd");
    vector<string> vec_a = {"a", "abc", "b", "ab", "cd", "bcd", "d", "c" };
    cout << "===========================" << endl;
    vector<string> result = WordBreak(str_a, vec_a);
    for (const auto& sentence : result) {
        cout << sentence << endl;
    }
    cout << "===========================" << endl;

    return 0;
}

===========================
a b c d
a b cd
a bcd
ab c d
ab cd
abc d
===========================