679

679. 24 Game (Hard)

You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

• The division operator '/' represents real division, not integer division.

  <ul>
  	<li>For example, <code>4 / (1 - 2 / 3) = 4 / (1 / 3) = 12</code>.</li>
  </ul>
  </li>
  <li>Every operation done is between two numbers. In particular, we cannot use <code>'-'</code> as a unary operator.
  <ul>
  	<li>For example, if <code>cards = [1, 1, 1, 1]</code>, the expression <code>"-1 - 1 - 1 - 1"</code> is <strong>not allowed</strong>.</li>
  </ul>
  </li>
  <li>You cannot concatenate numbers together
  <ul>
  	<li>For example, if <code>cards = [1, 2, 1, 2]</code>, the expression <code>"12 + 12"</code> is not valid.</li>
  </ul>
  </li>
  

Return true if you can get such expression that evaluates to 24, and false otherwise.

 

Example 1:

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

Example 2:

Input: cards = [1,2,1,2]
Output: false

 

Constraints:

• cards.length == 4
• 1 <= cards[i] <= 9

Companies:
Uber, Bloomberg, Apple

Related Topics:
Array, Math, Backtracking

Solution 1. DP

// OJ: https://leetcode.com/problems/24-game/
// Author: github.com/lzl124631x
// Time: O(?)
// Space: O(?)
class Solution {
    bool judge(vector<int> &A) {
        unordered_set<double> dp[4][4] = {};
        for (int i = 0; i < 4; ++i) dp[i][i].insert(A[i]);
        for (int i = 2; i >= 0; --i) {
            for (int j = i + 1; j < 4; ++j) {
                for (int k = i; k < j; ++k) {
                    for (double a : dp[i][k]) {
                        for (double b : dp[k + 1][j]) {
                            dp[i][j].insert(a + b);
                            dp[i][j].insert(a - b);
                            dp[i][j].insert(a * b);
                            if (b) dp[i][j].insert(a / b);
                        }
                    }
                }
            }
        }
        for (double n : dp[0][3]) {
            if (abs(n - 24) < 1e-6) return true;
        }
        return false;
    }
public:
    bool judgePoint24(vector<int>& A) {
        sort(begin(A), end(A));
        do {
            if (judge(A)) return true;
        } while (next_permutation(begin(A), end(A)));
        return false;
    }
};