꼰대 개발자~

문자열 리스트가 아래와 같이 존재 할때 

["a", "x", "n", "na", "b", "ba"]

"banana"로 조합되는 조합의 합은? ( 중복 사용 허용 )

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const string target = "banana";

int combination(vector<string> & data, const string & comb, vector<string> & results){
    int found = 0;
    for(auto itr=data.begin();itr!=data.end();itr++){
        vector<string> new_results(results);

        string new_comb = comb + *itr;
        if(new_comb.size() > target.size())
            continue;;
        
        auto p = target.find(new_comb);
        if(p != 0) continue;
        
        new_results.push_back(*itr);
        
        if(new_comb.size() == target.size()){
            cout << "FOUND (" << new_comb << ") : ";
            for(auto i=new_results.begin(); i!=new_results.end();i++){
                cout << *i;
                if(i+1 != new_results.end()){
                    cout << " - ";
                }
            }
            cout << endl;
            
            found++;
            continue;
        }
        
        found += combination(data, new_comb, new_results);
    }
    return found;
}

int main(int argc, const char * argv[]) {
    vector<string> data = {
        "a", "x", "n", "na", "b", "ba"
    };
    
    vector<string> results;
    
    int result_count = combination(data, "", results);
    cout << "result_count : " << result_count << endl;
    
    return 0
}

결과

FOUND (banana) : b - a - n - a - n - a
FOUND (banana) : b - a - n - a - na
FOUND (banana) : b - a - na - n - a
FOUND (banana) : b - a - na - na
FOUND (banana) : ba - n - a - n - a
FOUND (banana) : ba - n - a - na
FOUND (banana) : ba - na - n - a
FOUND (banana) : ba - na - na

result_count : 8