Leetcode 679: 24 Game

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.

Problem Analysis:

We don’t know the cards whether can get the value of 24 until we judge all possible computation of card combination.

So the key is to iterate all possible computations. To simplify it, we note that there are only 4 cards. We can permute the cards every time, and choose 2 of them to compute with operator then become 3 cards, then choose 2 of 3 cards to compute with operator to become 2 cards, at last compute the 2 cards with operator to become 1 value, check it is 24?

Solution:

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        do {
            if (isValid(nums)) return true;
        } while (next_permutation(nums.begin(), nums.end()));
        
        return false;
    }
    
    bool isValid(vector<int>& nums) {
        if (isValid(nums[0] + nums[1], nums[2], nums[3]) || 
           isValid(nums[0] - nums[1], nums[2], nums[3]) || 
           isValid(nums[0] * nums[1], nums[2], nums[3]) || 
           ((nums[1] != 0) && isValid(nums[0] / (double)nums[1], nums[2], nums[3])))
            return true;
        if (isValid(nums[0], nums[1] + nums[2], nums[3]) || 
           isValid(nums[0], nums[1] - nums[2], nums[3]) || 
           isValid(nums[0], nums[1] * nums[2], nums[3]) || 
           ((nums[2] != 0) && isValid(nums[0], nums[1] / (double)nums[2], nums[3])))
            return true;
        if (isValid(nums[0], nums[1], nums[2] + nums[3]) || 
           isValid(nums[0], nums[1], nums[2] - nums[3]) || 
           isValid(nums[0], nums[1], nums[2] * nums[3]) || 
           ((nums[3] != 0) && isValid(nums[0], nums[1], nums[2] / (double)nums[3])))
            return true;
        return false;
    }
    
    bool isValid(double a, double b, double c) {
        if (isValid(a + b, c) || isValid(a - b, c) || isValid(a * b, c) || b && isValid(a / b, c))
            return true;
        if (isValid(a, b + c) || isValid(a, b - c) || isValid(a, b * c) || c && isValid(a, b / c))
            return true;        
        return false;
    }
    
    bool isValid(double a, double b) {
        if (abs(a + b - 24.0) < 0.001 || abs(a - b - 24.0) < 0.001 || abs(a * b - 24.0) < 0.001 || b && abs(a / b - 24.0) < 0.001)
            return true;
        return false;
    }
};

Time Complexity: O(nlgn)

Space Complexity: O(1)