Leetcode 679: 24 Game

https://leetcode.com/problems/24-game/description/

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

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

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Notes:

This question can be solved by DFS (brutal force version). But here I want to share another solution using Divide and Conquer.

In some sense, due to the using of (), this question is similar to Leetcode 241: Different Ways to Add Parentheses.

First step, we can get all the permutations of the four numbers.

Then for each permutation, we can run divide and conquer to get all the possible results. The key is how to divide them first and then merge them back.

See the code below:

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        double epslon = 0.00001;
        vector<vector<int>> allPermu = findAllPermu(nums);
        for(auto &a : allPermu) {
            vector<double> res = findAll(a, 0, (int)nums.size()-1);
            for(auto &a : res) {
                if(abs(a-24)<epslon) return true;
            }
        }
        return false;
    }

private:
    vector<vector<int>> findAllPermu(vector<int>& nums) {
        set<vector<int>> res;
        int len = nums.size();
        vector<bool> visit(len, false);
        vector<int> temp;
        dfs(nums, visit, temp, res);
        return vector<vector<int>> (res.begin(), res.end());
    }

    void dfs(vector<int>& nums, vector<bool>& visit, vector<int>& ts, set<vector<int>>& res) {
        if(ts.size() == nums.size()) {
            res.insert(ts);
            return;
        }
        for(int i=0; i<nums.size(); ++i) {
            if(visit[i]) continue;
            visit[i] = true;
            ts.push_back(nums[i]);
            dfs(nums, visit, ts, res);
            ts.pop_back();
            visit[i] = false;
        }
    }

    vector<double> findAll(vector<int>& nums, int left, int right) {
        if(left > right) return {};
        if(left == right) return {(double)nums[left]};
        set<double> res;
        for(int i=left; i<right; ++i) {
            auto lvs = findAll(nums, left, i);
            auto rvs = findAll(nums, i+1, right);
            for(auto &a: lvs) {
                for(auto &b: rvs) {
                    res.insert(a+b);
                    res.insert(a-b);
                    res.insert(a*b);
                    if(b != 0.0) res.insert(a/b);
                }
            }
        }
        return vector<double> (res.begin(), res.end());
    }
};