24 Game


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) < 1e6; 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; } };

@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.



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

@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 thatn
is a constant (4 in your example) ?



@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!/((nr)!) = 4!/((42)!) = 432/2 = 12