給定一個整數n和一個由不同大寫字母組成的字元串str

       采用回溯法。首先把解空間樹設成5層strlen(str)叉樹，然後深度優先搜尋這棵樹，如果周遊發現正在周遊的結點所代表的的字母已經在current[]中，則剪枝，否則把該節點存進current[]裡面。周遊到葉子結點時，首先判斷current[]裡面的字母是否滿足題意，如果不滿足則回溯，如果滿足則判斷該字典序是否大于原來已經找到的best[]，如果是則把best[]的内容替換為current[]的，否則回溯。

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int M = 100;
const int N = 100;
char best[6] = { '\0' };
char current[6] = { '\0' };

bool is_in_str(char c, char str[], int n)       //判斷c是否在str[]裡面
{
    for (int i = 0; i < n; i++)
    {
        if (str[i] == c)
            return true;
    }
    return false;
}

void traceback(int n, char str[], int t)
{
    if (t == 5)     //到達解空間樹的葉子結點
    {
        int s = 0;
        for (int i = 0; i < 5; i++)
        {
            s += (int)(pow(current[i] - 'A' + 1, i + 1) * pow(-1, i));
        }
        if (s == n)
        {
            if (best[0] == '\0' || strcmp(best, current) < 0)       //如果所得到的解的字典序比原來best[]存儲的要大，則best[]存儲這個解
            {
                strcpy(best, current);
            }
        }
    }
    else if (t < 5)
    {
        for (unsigned int i = 0; i < strlen(str); i++)
        {
            if (!is_in_str(str[i], current, t))     //所得到的解裡面不能有重複字母
            {
                current[t] = str[i];
                traceback(n, str, t + 1);
                current[t] = '\0';
            }
        }
    }
}

int main(void)
{
    int n[M] = { 0 };
    char str[M][N] = { '\0' };
    int check, i, k;
    i = 0;
    k = 0;
    cin >> check;
    while (check != 0)      //檢查輸入的n是否為0
    {
        n[k] = check;
        cin >> str[k];
        k++;
        cin >> check;
    }

    for (int i = 0; i < k; i++)     //對輸入的每一行進行計算
    {
        traceback(n[i], str[i], 0);
        if (best[0] == '\0')
            cout << "no solution" << endl;
        else
            cout << best << endl;

        for (int j = 0; j < 6; j++)     //計算完每一行後要對best[]和current[]重新設為初始值
        {
            best[j] = '\0';
            current[j] = '\0';
        }
    }
 
    return 0;
}