回溯法：雀魂启动！

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

题解：

        回溯法

        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 //递归，如果剩余的牌能够和牌，返回true if (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]--; //递归，如果剩余的牌能够和牌，返回true if (is_valid(cards)) { //回溯 cards[i]++; cards[i + 1]++; cards[i + 2]++; return true; } //回溯 cards[i]++; cards[i + 1]++; cards[i + 2]++; } } //走到这里有两种可能： // 1、有剩下的牌 -- 无法和牌返回false // 2、没剩下牌 -- 和牌返回true for (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; }