题解 | #雀魂启动！#

题目分析
根据手上已有的 13 张牌，求从剩余的 23 张牌中抽取一张牌构成和牌的解。因此，从问题的要求中可以看出，该题的核心问题在于如何判断给定 14 张牌是否和牌。
求解思路
给定 14 张牌，判断是否和牌，题目和牌要求如下：

• 14张牌中有2张相同数字的牌，称为雀头。
• 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）

我们经过粗略的思路，发现 14 张牌能构成的排列组合情况十分多，一一列举实属不可能。因此，我的大致一个思路便是使用搜索，使用简单的 for 循环肯定不可能求解，因为使用 for 无法表示问题的求解的入口和出口情况。因为，14 四张卡牌构成和牌的情况只有 3 种（1、雀头；2、刻子；3、顺子），我们可以把每张牌分别去构成这 3 种和牌的组合（如果可以的话）；然后从牌组中消去该组合，再去判断剩余的牌是否还能构成这 3 中组合；如果，最后无剩余的牌，那么就代表这 14 张牌是可以和牌的；我们需要尝试所有的情况。
因此，从上面的分析可以看出，递归是我们求解该问题的一个确定方向。
问题求解
经过上面的分析，需要使用递归。每轮递归中，需要分别判断当前剩余牌中的 3 种可能组合形式，直至无牌（代表可以和牌）；或者每种情况都会剩余牌的话（代表不可以和牌）。

注意：问题其实有一个特殊要求：雀头只能出现一次。因此在递归中，如果已经有雀头了就不需要再组合成雀头，这里我使用了参数 haveQueTou 来表示是否已有雀头，count 记录每张牌对应的数量，ans 记录是否能构成雀头，默认是不能，card 记录了 14 张牌。

具体求解：可以参考下面的代码和注释，你一定能看懂的！

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

//递归回溯判断给定 14 张牌是否可以和牌，每次从 card[0] 位置处进行三种牌的组合
void dfsHePai(vector<int>& card,vector<int>& count,bool haveQueTou,bool& ans){
    if(card.empty()){
        //如果 14 张卡牌能为空，代表可以和牌
        ans = true;
        return;
    }
    //因为游戏规则限定有三种组合方式：1、雀头(两张相同卡牌)；2、顺子(连续三张牌)；3、刻子(三个一样的牌);
    //和牌的要求必须存在一个雀头、其他的为顺子或者刻子即可
    if(!haveQueTou && count[card[0]] >= 2){
        //如果可以构成雀头，先构成雀头
        haveQueTou = true;                                            //代表已经存在雀头
        vector<int> tempCard(card.begin() + 2,card.end());            //去掉前两个元素
        count[card[0]] -= 2;                                          //计数减 2
        dfsHePai(tempCard,count,haveQueTou,ans);                          //判断后面的牌是否能和牌
        haveQueTou = false;
        count[card[0]] += 2;                                          //还原
    }
    if(count[card[0]] > 2){
        //如果可以构成刻子，使该牌构成刻子
        vector<int> tempCard(card.begin() + 3,card.end());
        count[card[0]] -= 3;
        dfsHePai(tempCard, count, haveQueTou,ans);
        count[card[0]] += 3;
    }
    if(card[0] < 8 && count[card[0] + 1] > 0 && count[card[0] + 2] > 0){
        //如果可以用第一个卡牌后面两个卡牌构成顺子的话
        --count[card[0]];                                //当前卡牌 card[0] 计数减一
        --count[card[0] + 1];                            //后面一个卡牌 card[0] + 1 计数减一
        --count[card[0] + 2];                            //后面第二个个卡牌 card[0] + 2 计数减一
        vector<int> tempCard;                            //card 中删除这三张卡牌
        for(int i = 1; i < 10; ++i)
            for(int j = 0; j < count[i]; ++j)
                tempCard.push_back(i);
        dfsHePai(tempCard,count, haveQueTou, ans);
        //还原现场，进行后面的搜索
        ++count[card[0]];                                //当前卡牌 card[0] 计数减一
        ++count[card[0] + 1];                            //后面一个卡牌 card[0] + 1 计数加一
        ++count[card[0] + 2];                            //后面第二个个卡牌 card[0] + 2 计数加一
    }
}

int main(){
    vector<int> count(10,0);                 //每张牌的数量
    for(int i = 0; i < 13; ++i){
        int c;
        cin >> c;
        ++count[c];
    }
    //分别判断最后一张为 i 时，是否和牌
    for(int i = 1; i <= 9; ++i){
        if(count[i] == 4)
            //代表手上的 14 张牌中牌 i 已经有 4 张，无法再抽到该牌
            continue;
        ++count[i];
        vector<int> card;                        //表示十四张牌且十四张牌是按从小到大的顺序排列
        for(int i = 1; i < 10; ++i){
            for(int j = 0; j < count[i]; ++j)
                card.push_back(i);
        }
        bool ans = false;
        dfsHePai(card, count, false,ans);
        if(ans)
            cout << i << ' ';
        --count[i];
    }
}