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

糖逗

题目描述：

1. 你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: [4, 1, 8, 7]
   
6. 输出: True
   
7. 解释: (8-4) * (7-1) = 24
   
8. 示例 2:
   
9. 
   
10. 输入: [1, 2, 1, 2]
    
11. 输出: False
    
12. 注意:
    
13. 
    
14. 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
    
15. 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
    
16. 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
    
17. 
    
18. 来源：力扣（LeetCode）
    
19. 链接：https://leetcode-cn.com/problems/24-game
    
20. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include<vector>
   
3. #include<cmath>
   
4. 
   
5. using namespace std;
   
6. 
   
7. void dfs(vector<double>&input, bool& res){
   
8.         if (input.size() == 1) {
   
9.             if (abs(input[0] - 24) < 0.0001) res = true;
   
10.             return;
    
11.         }
    
12.         for(int i = 0; i < input.size(); i++){
    
13.                 for(int j = 0; j < i; j++){
    
14.                         double temp1 = input[i], temp2 = input[j];
    
15.                        
    
16.                         vector<double> temp {temp1 + temp2, temp1 - temp2, temp2 - temp1, temp1 * temp2};
    
17.                         if(temp2 > 0.0001) temp.push_back(temp1 / temp2);
    
18.                         if(temp1 > 0.0001) temp.push_back(temp2/temp1);
    
19.                         input.erase(input.begin() + i);
    
20.                         input.erase(input.begin() + j);
    
21.                         for(int i = 0; i < temp.size(); i++){
    
22.                                 input.push_back(temp[i]);
    
23.                                 dfs(input, res);
    
24.                                 input.pop_back();
    
25.                         }
    
26.                         input.insert(input.begin() + j, temp2);
    
27.                         input.insert(input.begin() + i, temp1);
    
28.                        
    
29.                        
    
30.                 }
    
31.         }
    
32. }
    
33. 
    
34. 
    
35. bool solution(vector<int>&num){
    
36.         bool res = false;
    
37.         vector<double> input (num.begin(), num.end());
    
38.         dfs(input, res);
    
39.         return res;
    
40. }
    
41. 
    
42. 
    
43. int main(void){
    
44.         vector<int> input;
    
45.         int number;
    
46.         while(cin >> number){
    
47.                 input.push_back(number);
    
48.         }
    
49.         cout << solution(input) << endl;
    
50.         return 0;
    
51. }

复制代码

注意事项：
1.

1. input.insert(input.begin() + j, temp2);
   
2.                         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/