描述

题目描述

给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且不考虑括号运算

此题允许数字重复，如3 3 4 4为合法输入，但是每个数字只允许使用一次，如此处一共有两个3，则运算过程中两个3都被选取计算一次，所以3被调用运算两次，但是对应读入的两个数字

示例

输入：
7 2 1 10
输出：
true

知识点：搜索，DFS，回溯

难度：⭐⭐⭐

题解

方法一：DFS

图解：

算法流程：

• 通过递归+dfs，首先定义递归函数功能：当前已经使用了数组的u个数字，前面数字的运算结果为tmp，返回是否运算结果为24
• 确定递归终止条件：已经使用了数组四个元素，同时结果为24，满足题意
• 通过加减乘除四种运算，加减乘除当前数字num[i]，不断递归运算，直到已经使用了数组四个元素，同时结果为24，满足题意

Java 版本代码如下：

import java.util.*;
import java.io.*;
public class Main{
    static int[] nums = new int[4];
    static boolean[] visit = new boolean[4];
    static int flag = 0;
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String[] a = in.nextLine().split(" ");
            for(int i = 0; i < 4; i ++)
                nums[i] = Integer.parseInt(a[i]);
            dfs(0, 0);   
            System.out.println( flag == 1 );
        }

    }

    // tmp是前面n个数字运算结果，u表示已经使用了多少个数字
    static boolean dfs(int u,float tmp){
        // 递归终止条件：已经使用了数组四个元素，同时结果为24，满足题意
        if(tmp == 24 && u == 4){
            flag = 1;
            return true;
        }

        for(int i = 0; i < 4; i ++){
            if(visit[i] == false){
                visit[i] = true;
                // 加减乘除当前数字num[i]
                if( dfs(u + 1, tmp + nums[i]) ||
                   dfs(u + 1, tmp - nums[i])  ||
                   dfs(u + 1,tmp * nums[i]) ||
                   dfs(u + 1, tmp / nums[i])){
                    return true;
                }
                // 相当于回溯
                visit[i] = false;
            }
        }
        return false;
    }
}

复杂度分析：

时间复杂度：$O(1)O(1)$，因为n=4，则我们即便搜索过所有的情况，那么我们最后的次数也是一个常数级别

空间复杂度：$O(1)O(1)$，因为n=4，而且我们的递归栈使用的空间也是非常小，是一个常数级别

方法二：暴力穷举

版本代码如下：

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

vector<double> a(4);
vector<char> op = { '+', '-', '*', '/' };
vector<vector<char>> all;
// a数组是用来存储我们输入的四位数字的
// 我们的op数组是我们的四个符号位的一个数组
// 我们这个表达式里面一共是需要三个符号的
// 我们的这个all就是我们四个选项选三个然后排列组合的所有的可能

void init()
{
    for (auto& it1 : op) { 
        // it1代表的是我们第一个的符号位是什么
        for (auto& it2 : op) {
            // it2代表的是我们第二个的符号是什么
            for (auto& it3 : op) {
                // it3代表的是我们第三个符号位是什么
                vector<char> tmp(3);
                // 这里我们开辟的tmo是我们临时的一个存储三个符号位的数组
                tmp[0] = it1, tmp[1] = it2, tmp[2] = it3;
                // 我们将我们枚举出来的符号位放到这个数组里面
                all.push_back(tmp);
                // 然后将我们的可能塞入我们的这个all的数组中
            }
        }
    }
}

double cal(double a, double b, char op)
{
    switch (op) {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    }
    return 1;
}
// 这个是用来计算值的，判断我们的符号然后进行一个运算

void solve()
{
    sort(a.begin(), a.end());
    // 因为我们的c++内的全排列函数要求是要从小到大的数组，所以我们排一下序
    do {
        for (auto &it : all) {
            // 遍历所有的符号集的所有可能
            double res = a[0];
            // 因为我们有四个数字，但是只有三个符号，所以我们先把答案设置为第一个数字
            int index = 0;
            // 这个是我们符号数组的下标
            for (int i = 1; i <= 3; i++)
                res = cal(res, a[i], it[index++]);
            // 计算我们当前这个符号集下的答案会是多少
            if (res == 24) {
                cout << "true\n";
                return; 
            }
            // 如果已经是等于了24，那么我们可以不用管其他的了，直接就是可以把他输出，然后退出即可
        }
    } while (next_permutation(a.begin(), a.end()));
    // 这个是我们执行了一个全排列
    cout << "false\n";
    // 执行完了所有的都没有答案，我们输出false
}

signed main()
{
    init();
    while (cin >> a[0] >> a[1] >> a[2] >> a[3]) {
        solve();
    }
    return 0;
}

复杂度分析：

时间复杂度：$O(1)O(1)$，因为n=4，最后的全排列后，也是一个常数

空间复杂度：$O(1)O(1)$，因为n=4，n非常的小，所以我们的空间复杂度可以看成O(1)