題目鏈接：雀魂啟動(dòng)！_牛客題霸_?？途W(wǎng)

題解：

? ? ? ? 回溯法

? ? ? ? 1、用哈希思想構(gòu)建映射表，標(biāo)記已有的卡的種類和個(gè)數(shù)

? ? ? ? 2、遍歷卡池，先從卡池中抽一張卡，因?yàn)橹荒艹橐粡埧?#xff0c;所以一種卡只判斷一次

? ? ? ? 3、抽到卡后找雀頭 -- 遍歷已有卡，使用窮舉法，如果手中有一種卡的數(shù)量達(dá)到兩張，選其作為雀頭

? ? ? ? 4、找到雀頭后找順子和刻子 --?再次遍歷已有卡，如果手中有一種卡的數(shù)量達(dá)到三張，選其作為刻子；如果有三種卡是連號(hào)，選其作為順子

? ? ? ? 5、如果全部配對(duì)完后手里的卡沒了，那么恭喜你和牌；如果手中還有牌剩余，那就回溯重新找

有很多細(xì)節(jié)思路中沒提到，代碼中都有注釋，求一個(gè)贊！！

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;vector<int> res;bool is_valid(vector<int>& cards) {//繼續(xù)窮舉for (int i = 1; i <= 9; i++) {//先找順子if (cards[i] >= 3) {cards[i] -= 3;//遞歸，如果剩余的牌能夠和牌，返回true//遞歸，如果剩余的牌能夠和牌，返回trueif (is_valid(cards)) {//回溯cards[i] += 3;return true;}//回溯cards[i] += 3;}//再找刻子if (i <= 7 && cards[i] > 0 && cards[i + 1] > 0 && cards[i + 2] > 0) {cards[i]--;cards[i + 1]--;cards[i + 2]--;//遞歸，如果剩余的牌能夠和牌，返回trueif (is_valid(cards)) { //回溯cards[i]++;cards[i + 1]++;cards[i + 2]++;return true; }//回溯cards[i]++;cards[i + 1]++;cards[i + 2]++;}}//走到這里有兩種可能：//  1、有剩下的牌 -- 無法和牌返回false//  2、沒剩下牌 -- 和牌返回truefor (int i = 1; i <= 9; i++) {if (cards[i] > 0) {return false;}}return true;
}bool head(vector<int>& cards) {//如果有兩張一樣的牌，先嘗試作為雀頭for (int i = 1; i <= 9; i++) {if (cards[i] >= 2) {cards[i] -= 2;//再用遞歸回溯從，剩余牌中找順子和刻子，如果能和牌，代表這次抽取成功，打印記錄if (is_valid(cards)) {//回溯 -- 這里return了就不走到70行回溯，那么找下一種組合的時(shí)候就會(huì)少兩張牌，大漏洞cards[i] += 2;return true;}//回溯cards[i] += 2;}}//走到這代表沒有雀頭，寄return false;
}void check(vector<int>& cards) {//抽一張，窮舉法for (int i = 1; i <= 9; i++) {//如果有一張牌的數(shù)量小于4，代表可以抽這張牌，進(jìn)行窮舉if (cards[i] < 4) {//抽取cards[i]++;//繼續(xù)窮舉選擇雀頭if (head(cards)) {res.push_back(i);}//回溯cards[i]--;}}
}int main() {//哈希表存放已有的牌vector<int> cards(10);//抽取13張牌for(int i=0;i<13;i++){int n;cin>>n;cards[n]++;}//回溯法檢查和牌check(cards);//防止順序不一樣，排下序 -- res是全局變量，懶得傳參了sort(res.begin(),res.end());for(auto v : res){cout << v <<" ";}return 0;}