# 24 Game

• can you provide c++ solution, thanks

• @codingcrazer

``````class Solution {
public:
bool judgePoint24(vector<int>& nums) {
vector<double> A;
for (int v: nums) A.push_back(v);
return solve(A);
}
bool solve(vector<double>& A) {
if (A.empty()) return false;
if (A.size() == 1) return abs(A[0] - 24) < 1e-6;

for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < A.size(); j++) if (i != j) {
vector<double> B;
for (int k = 0; k < A.size(); k++) {
if (k != i && k != j) B.push_back(A[k]);
}
for (int k = 0; k < 4; k++) {
if (k == 0) B.push_back(A[i] + A[j]);
if (k == 1) B.push_back(A[i] - A[j]);
if (k == 2) B.push_back(A[i] * A[j]);
if (k == 3 && A[j] != 0) B.push_back(A[i] / A[j]);
if (solve(B)) return true;
B.pop_back();
}
}
}
return false;
}
};
``````

• ``````import Data.List (permutations)

ops = [(+), (-), (*), (/)]

solve ns = not . null \$ do
[x, y, z, w] <- permutations ns
f <- ops
g <- ops
h <- ops
guard \$ f (g (h x y) z) w == 24
|| f (g x y) (h z w) == 24
|| f x (g y (h z w)) == 24
``````

• Can someone explain to me why there are 12∗6∗2∗4∗4∗4 possibilities?

• @okdolly Say we have numbers a, b, c, d. We choose two of them (with order) in 12 ways and perform one of 4 operations. This is where 12 * 4 comes from. Then, with 3 remaining numbers, we choose 2 of them and perform one of 4 operations. This is where 6 * 4 comes from. Finally we have two numbers left and make a final choice of 2 * 4 possibilities.

• Could you please explain how you came up with that upper bound?

• @saiha It's 12 * 6 * 2 * 4 * 4 * 4.

• @awice Thank you so much!

• Does the space complexity count the number of recursion function in heap?

• @isucs Yes. In terms of `n`, the number of initial numbers we have, the heap could get as big as `O(4^n n! (n-1)!)` or so. But if we have considered `n` to be a constant (like `4`), then this would still be considered an O(1) factor.

• This post is deleted!

• @awice You descirbe `n` as the number of initial numbers we have, it is not the number of operations we have, why do you think you could consider that `n` is a constant (4 in your example) ?

• I'm looking at the Java code, and I don't see it taking into account `nums.get(j) - nums.lget(i)` and `nums.get(j)/nums.get(i)`. Am I missing something?

• @richard.zhang.969 In the initial loops, i could be greater than j already.

• @awice Thanks for pointing that out. Totally missed that.

• "we choose two numbers (with order) in 12 ways " This is wrong, right? it should be 9 * 9 = 81.

• @cygnus For example say the numbers are `(a, b, c, d)`. The 12 ways are `(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)` and the other 6 reflections `(b, a), (c, a), (d, a), (c, b), (d, b), (d, c)`.

• @cygnus in another way, it is a permutational problem. Choosing 2 numbers from 4 is 4C2 which is n!/((n-r)!) = 4!/((4-2)!) = 432/2 = 12

• what does chose two numbers with order mean here? I'm a little confused

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.