变位词回溯算法

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
void findA(int index,vector<string> &anag);

    int n = 2;//字典词的个数
    string lexicon[] = {"MA","YINGJIEXII"};//字典数组
    int m = 3;//
    string word[] = {"I","AM","XIYINGJIE"};;
    string phrase = "I AM XIYINGJIE";
    int letters[26];

int main(){
    //统计字母出现的频数
    for(int i = 0;i<phrase.length();i++){
        if(phrase[i] == ' ') continue;
        letters[phrase[i] - 'A']++;
    }
    vector<string> anag;
    findA(0,anag);
    cin>>n;

    return 0;
}

void findA(int index,vector<string> &anag){
    bool find = true;
    for(int i = 0;i<26;i++){
        if(letters[i]>0){
            find = false;
            break;
        }
    }
    if(find){
        //将变位词构成字符串
        string s;
        for(int i = 0;i<anag.size();i++){
            if(i>0) s+= " ";
            s += anag[i]; 
        }
        if(s!=phrase) cout<<phrase<<" = "<<s<<endl;
        return;

    }
    int alpha[26];
    for(int i = index;i<n;i++){
        memset(alpha,0,sizeof(alpha));
        bool more = true;
        for(int j = 0;j<lexicon[i].length();j++){
            int a = lexicon[i][j] - 'A';
            alpha[a] ++;
            //一个字母的频数超过了短语中的字母频数，该条目无效；
            if(alpha[a]>letters[a]){
                more = false;
                break;
            }
        }
        //该条目有效，则回溯搜索
        if(more){
            //将该条目的单词数减去
            for(int j =0;j<26;j++){
                letters[j] -= alpha[j];
            }
            //将该条目加入到变位词数组中
            anag.push_back(lexicon[i]);
            //回溯
            findA(i,anag);
            //回复回溯前的状态
            anag.pop_back();
            for(int j = 0;j<26;j++){
                letters[j] += alpha[j];
            }
        }
    }
}