题目描述

给定四张卡片，可以使用’(‘, ‘)’ , ‘+’ , ‘-‘ , ‘*’, ‘/’四种运算符，问是否能够组成24点。

样例

Input: [4, 1, 8, 7]
Output: True
答案: (8-4) * (7-1) = 24

算法

(递归)

首先括号可以忽略，因为我们可以从数组中任意取数，所以括号没什么用。
第一步，我们选两个数，进行加减乘除，然后变成三个数的组合。
第二步，我们选两个数，进行加减乘除，然后变成两个数的组合。
第三步，我们选择两个数，进行加减乘除，然后变成1个数的组合。
最后我们看一个数的组合里面有没有24就可以了。
这就是所有有可能的情况。

时间复杂度分析：
第一步：C(2)(4) * 6 = 36
第二步：C(2)(3) * 6 = 18
第三步：C(2)(2) * 6 = 6
总共 36 * 18 * 12 = 3888种情况。
注意，这里的a+b和b+a，以及ab和ba实际上是一种结果。
否则为
第一步：C(2)(4) * 8 = 48
第二步：C(2)(3) * 8 = 24
第三步：C(2)(2) * 8 = 8
总共 48 * 24 * 8 = 9216种情况。

C++ 代码

class Solution {
public:
    vector<double> create(const vector<double> &n, double next){
        vector<double> nt = n;
        nt.push_back(next);
        return nt;
    }

    bool find(vector<double> n ){
        if (n.size()==1) 
            return abs(n[0]-24.0) < (1e-9);

        bool ret = false;

        for (int i =0; i<n.size();++i ){
            for (int j = i+1;j<n.size();++j){
                vector<double> new_n,fin;
                for (int k = 0;k<n.size();++k)
                    if (k != i && k != j )
                        new_n.push_back(n[k]);

                double a = n[i];
                double b = n[j];

                fin = create(new_n,a+b);
                ret |= find(fin);

                fin = create(new_n,a-b);
                ret |= find(fin);

                fin = create(new_n,b-a);
                ret |= find(fin);

                fin = create(new_n,a*b);
                ret |= find(fin);

                if (abs(b) > 1e-8){
                    fin = create(new_n,a/b);
                    ret |= find(fin);
                }

                if (abs(a) > 1e-8){
                    fin = create(new_n,b/a);
                    ret |= find(fin);
                }

            }
        }
        return ret;

    }
    bool judgePoint24(vector<int>& nums) {
        vector<double> n;
        for (int i = 0;i<nums.size();++i)
            n.push_back(nums[i]);

        return find(n);
    }
};