A "hard" Leetcode problem with a stupidly efficient solution

Published on 30/03/2025

Leetcode has a hard problem called 24 Game. It has the following requirements:

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.

For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.

Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.

For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.

You cannot concatenate numbers together

For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.

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

Intuition

Since the input size is limited to 4 numbers and values from 1 to 9, it might make sense to precalculate the solution in some lookup table instead of doing expensive brute force.

Approach

Since inputs are arrays of 4 numbers in the range of [1, 9], they can be easily encoded as 4 digit numbers just by concating their elements. With the naive approach you would have to handle 9 * 9 * 9 * 9 = 6561 input combinations. However, considering that the input number permutations don't affect the answer (for example [1, 7, 2, 3] will give the same answer as [1, 2, 3, 7]) we can only handle the inputs with sorted numbers. This alone reduces the number of combinations to 495. Furthermore, if we only handle the false answers, we have to handle only 91 combinations!

So you simply need to have some hash table based set with that 91 input combinations which give false answer. When getting input, you need to sort its numbers and encode in integer. And if that integer is in the set, the answer is false, otherwise the answer is true.

Is this cheating?

You might think this is cheating and it's dishonest, I kinda agree. The purpose of this problem is to test if you can write a backtracking solution, especially considering that the number of the combinations is small and the execution duration will be within a statistical noise. On top of that, I don't think this will scale well for larger inputs (a huge consumption of static memory because of the exponential(ish) explosion of the combinations' number), so the backtracking is the most honest solution, even though this is much more compact and efficient in this case.

Complexity

Time complexity: O(1)
Space complexity: O(1)

Code (C++)

unordered_set<int> ans{
	1111,1112,1113,1114,1115,1116,1117,1119,1122,1123,1124,1125,1133,
	1159,1167,1177,1178,1179,1189,1199,1222,1223,1299,1355,1499,1557,
	1558,1577,1667,1677,1678,1777,1778,1899,1999,2222,2226,2279,2299,
	2334,2555,2556,2599,2677,2777,2779,2799,2999,3358,3467,3488,3555,
	3577,4459,4466,4467,4499,4779,4999,5557,5558,5569,5579,5777,5778,
	5799,5899,5999,6667,6677,6678,6699,6777,6778,6779,6788,6999,7777,
	7778,7779,7788,7789,7799,7888,7899,7999,8888,8889,8899,8999,9999
};

class Solution {
public:
	Solution() {
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);
	}
	bool judgePoint24(vector<int>& cards) {
		sort(cards.begin(), cards.end());
		int num = cards[0] * 1000 + cards[1] * 100 + cards[2] * 10 + cards[3];
		return ans.find(num) == ans.end();
	}
};

I also posted this solution here.

Previous Next