题目的主要信息：

给出4个1-10的数字，通过加减乘除，得到数字为24就输出true，否则false
数字允许重复，但每个数字仅允许使用一次，测试用例保证无异常数字

方法一：穷举遍历

具体做法：

四个数字，如下图，一共需要3个运算符，我们可以遍历这个位置的4种运算，计算每种组合的结果，查看是否等于24，同时因为数字的次序可以不确定，我们还需要对这四个数字进行全排列，将全排列的每种结果放入下面的数字框中，与不同的运算符搭配，这样就穷举了所有的可能性，如果这里面都不能组成24，那就是不可能。

alt

注意：调用next_permutation获取全排列的数组必须是由小到大开始的，因此要先排序。

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

double cal(double a, double b, char c){ //根据运算符运算结果
    switch(c){
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
    }
    return 0;
}

bool check(vector<double>& nums){
    char op[4] = {'+', '-', '*', '/'};
    sort(nums.begin(), nums.end()); //先按照从小到大排
    do{
          for(int i = 0; i < 4; i++) //遍历三个位置的所有可能运算符
              for(int j = 0; j < 4; j++)
                  for(int k = 0; k < 4; k++){
                      double first = cal(nums[0], nums[1], op[i]); //依次运算
                      double second = cal(first, nums[2], op[j]);
                      if(cal(second, nums[3], op[k]) == 24) //判断是否等于24
                          return true;
                  }
      }while(next_permutation(nums.begin(), nums.end())); //依次找到其他排列
    return false;
}

int main(){
    vector<double> nums(4); 
    while(cin >> nums[0] >> nums[1] >> nums[2] >> nums[3]){ //输入4个数字
        if(check(nums))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，4个数字，3个运算符不管怎么全排列，都是常数时间
空间复杂度： $O (1)$ ，无额外空间

方法二：递归搜索

具体做法：

我们也可以用递归的方式搜索，每次完整4个数字送入递归函数，使用其中一个数字添加运算符进行运算，就将数组中去掉这个数字，然后继续递归，最后判断数组为空时结果是否等于24. 需要注意，因为要回溯，所以不能直接去掉原数组中的数字，而是拷贝一份备份来去除。

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

bool check(vector<double> nums, double result){ //递归检查能否组成24
    if(nums.empty()) //数组为空，判断等不等于24
        return result == 24;
    for(int i = 0; i < nums.size(); i++){ //遍历剩下的数字
        vector<double> rest(nums);
        rest.erase(rest.begin() + i); //删去使用的数字
        if(check(rest, result + nums[i]) //分别 进行加减乘除4种运算
          || check(rest, result - nums[i])
          || check(rest, result * nums[i])
          || check(rest, result / nums[i]))
            return true;
    }
    return false;
}

int main(){
    vector<double> nums(4); 
    while(cin >> nums[0] >> nums[1] >> nums[2] >> nums[3]){ //输入4个数字
        if(check(nums, 0))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，4个数字，不管怎么搜索回溯，都是常数时间
空间复杂度： $O (1)$ ，递归栈深度也为常数

题解 | #24点游戏算法#

题目的主要信息：

方法一：穷举遍历

方法二：递归搜索