Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 18

Description

24 Game

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>&#39;-&#39;</code> as a unary operator.
  <ul>
  	<li>For example, if <code>cards = [1, 1, 1, 1]</code>, the expression <code>&quot;-1 - 1 - 1 - 1&quot;</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>&quot;12 + 12&quot;</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

Solution

class Solution {
  const double EPS = 1e-7;
  bool solve(vector<double> &cards) {
    if(cards.size() == 1) return abs(cards[0] - 24) < EPS;

    int sz = cards.size();
    for(int i = 0; i < sz; ++i) {
      for(int j = 0; j < sz; ++j) {
        if(i == j) continue;

        vector<double> next;
        for(int k = 0; k < sz; ++k) {
          if(k == i || k == j) continue;
          next.push_back(cards[k]);
        }

        double a = cards[i];
        double b = cards[j];
        vector<double> candidates{a - b, a + b, b - a, a * b};
        if(abs(a) > EPS) candidates.push_back(b / a);
        if(abs(b) > EPS) candidates.push_back(a / b);
        for(auto val : candidates) {
          next.push_back(val);
          if(solve(next)) return true;
          next.pop_back();
        }
      }
    }
    return false;
  }
public:
  bool judgePoint24(vector<int>& cards) {
    vector<double> dcards(cards.begin(), cards.end());
    return solve(dcards);
  }
};

// Accepted
// 71/71 cases passed (63 ms)
// Your runtime beats 20.85 % of cpp submissions
// Your memory usage beats 17.49 % of cpp submissions (30.7 MB)