回溯法：雀魂启动！

题目链接：雀魂启动！_牛客题霸_牛客网

题解：

        回溯法

        1、用哈希思想构建映射表，标记已有的卡的种类和个数

        2、遍历卡池，先从卡池中抽一张卡，因为只能抽一张卡，所以一种卡只判断一次

        3、抽到卡后找雀头 -- 遍历已有卡，使用穷举法，如果手中有一种卡的数量达到两张，选其作为雀头

        4、找到雀头后找顺子和刻子 -- 再次遍历已有卡，如果手中有一种卡的数量达到三张，选其作为刻子；如果有三种卡是连号，选其作为顺子

        5、如果全部配对完后手里的卡没了，那么恭喜你和牌；如果手中还有牌剩余，那就回溯重新找

有很多细节思路中没提到，代码中都有注释，求一个赞！！

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;vector<int> res;bool is_valid(vector<int>& cards) {//继续穷举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行回溯，那么找下一种组合的时候就会少两张牌，大漏洞cards[i] += 2;return true;}//回溯cards[i] += 2;}}//走到这代表没有雀头，寄return false;
}void check(vector<int>& cards) {//抽一张，穷举法for (int i = 1; i <= 9; i++) {//如果有一张牌的数量小于4，代表可以抽这张牌，进行穷举if (cards[i] < 4) {//抽取cards[i]++;//继续穷举选择雀头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;}