C++刷leetcode（679. 24 点游戏）【深度优先搜索】

糖逗

题目描述：

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

示例 1:

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:

输入: [1, 2, 1, 2]
输出: False
注意:

除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/24-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

void dfs(vector<double>&input, bool& res){
        if (input.size() == 1) {
            if (abs(input[0] - 24) < 0.0001) res = true;
            return;
        } 
        for(int i = 0; i < input.size(); i++){
                for(int j = 0; j < i; j++){
                        double temp1 = input[i], temp2 = input[j];
                        
                        vector<double> temp {temp1 + temp2, temp1 - temp2, temp2 - temp1, temp1 * temp2};
                        if(temp2 > 0.0001) temp.push_back(temp1 / temp2);
                        if(temp1 > 0.0001) temp.push_back(temp2/temp1);
                        input.erase(input.begin() + i);
                        input.erase(input.begin() + j);
                        for(int i = 0; i < temp.size(); i++){
                                input.push_back(temp[i]);
                                dfs(input, res);
                                input.pop_back();
                        }
                        input.insert(input.begin() + j, temp2);
                        input.insert(input.begin() + i, temp1);
                        
                        
                }
        }
}


bool solution(vector<int>&num){
        bool res = false;
        vector<double> input (num.begin(), num.end()); 
        dfs(input, res);
        return res;
}


int main(void){
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        cout << solution(input) << endl;
        return 0;
} 

注意事项：
1.

input.insert(input.begin() + j, temp2);
                        input.insert(input.begin() + i, temp1);

上面的顺序不能反着，要正好和前面两句镜像对称
2. p-q q-p 包含了j+1到input.size（）的情况所以j取0到i即可。
3.bool后面一定要带&，因为res的值在运行dfs的时候可能会改变。
4.代码参考链接：https://leetcode-cn.com/problems ... su-fa-by-guohaodin/