回溯 part1【5】

24点游戏！！！

leetcode 679

 代码：

#include
#include
#include
using namespace std;
bool flag = false;//判断
char op[4] = { '+','-','*','/ ' };//运算符
const double minerror = 1e-6;//精度
void backtracking(vector& cards1)
{
    int length = cards1.size();
     if (length == 1)//如果 数组元素只有一个
    {
        if (abs(24.0 - cards1[0]) < minerror)//进行判断 精度小于1e-6就满足
            //if(a+b==24||a-b==24||b-a==24||a*b==24||(b!=0&&round(a/b)==24)||(a!=0&&round(b/a)==24))
            flag = true;//找到了
        return;//不论正确与否 返回
    }
     //随便挑选两个数
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            if (i == j)continue;//两个数不同
            //定义一个新数组，用来当下一个cards1，里面放的是 未取出的数，以及计算了的数
            vectornewcards;
            for (int k = 0; k < length; ++k) //把选剩下的先放进来
            {
                if (k != i && k != j)//如何判断是不是剩下的数
                    newcards.push_back(cards1[k]);
            }
            for (auto c : op)//从运算符中选择一个进行运算
            {
                if (c == '*')
                    newcards.push_back(cards1[i] * cards1[j]);//*法后计算的数
                else if (c == '+')
                    newcards.push_back(cards1[i] + cards1[j]);//+ 后计算的数
                else if (c == '-')
                {
                    newcards.push_back(cards1[i] - cards1[j]);// - 后计算的数
                }
                else
                {
                    if (cards1[j] == 0)return;
                    newcards.push_back(cards1[i] / cards1[j]);//除非 首先除掉0
                }
                backtracking(newcards);//递归，将新数组作为参数传进去进行相同运算操作
                newcards.pop_back();//如果不满足条件，把新数组里面最后一个计算的数拿出来，重新放入新值
                if (flag)return;//如果遇到了对的，就不需要再递归了，直接跳出。
            }
        }
    }
}
bool judgePoint24(vector& cards)
{
    vectorcards1;
    for (auto& card : cards)
    {
        cards1.push_back(card);
    }
    backtracking(cards1);
    return flag;
}
int n;
int main()
{
    
    int n;
    cin >> n;
    vectorcards(n,0);
    for (int i = 0; i < n; i++)
        cin >> cards[i];
    judgePoint24(cards);
    cout << flag;
	return 0;
}