Algorithm (Recursion)
- Let $f(V,x):\mathcal{P}(\{1,2,3,4\})\times\{\mathbb{R}\cup\emptyset\}\mapsto\{\texttt{true},\texttt{false}\}$ denote the possibility of reaching when currently number from set $V$ are used and current accumulated result being $x$. Let $M$ be the boolean monoid with OR operation.
- Then we have that $$f(V,x)=\begin{cases}
\texttt{Fold}_{M}\left(\texttt{List}\left[f(\{i,j\},\texttt{nums[i]}\otimes\texttt{nums[j]}))\right]\right) & \mathrm{if\ }x=V=\emptyset\\\\
\begin{split} & \texttt{Fold}_M\left(\texttt{List}\left[f(V\cup\{i,j\},(\texttt{nums[i]}\otimes\texttt{nums[j]})\otimes x):i,j\notin V\right]\right)\\\\
& \land\texttt{Fold}_M\left(\texttt{List}\left[f(V\cup\{i\},\texttt{nums[i]}\otimes x:i\notin V\right]\right)
\end{split}
& \text{if }x\neq\emptyset\\\\
\mathbb{I}(x=24) & \text{if }V=\{1,2,3,4\}
\end{cases}$$
- Thus, our desired solution is $f(\emptyset,\emptyset).$
- Note that since $V$ has at most $4$ elements, we can thus use bitset to simulate the real set in speed things up.
- Note that the evaluation of $f$ could also be done using a more traditional backtracking template.
Time Complexity
- It is a bit tedious to compute the exact number of total cases because there might be duplicates and cases there are equivalent due to communitativity of $+$ and $-$.
- Therefore, we in turn to compute an upper bound for all the cases: there are
- four numbers to choose without replacement;
- three operators to fill with replacement of $4$;
- $\binom{5}{2}$ ways to choose parenthesis.
3.Hence, in total there are at most $4!\times4^{3}\times\binom{5}{2}=15360$ ways to combine the numbers.
- As a result, the total time complexity is (really less than) $O(15360)$.
Memory
- We used two extra variables ($V$ and $x$) in each recursion call, the total memory is $O(15360).$
- Cost of recursion not counted since it could depend on compiler.
Code
template <class F>
struct recursive {
F f;
template <class... Ts>
decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward<Ts>(ts)...); }
template <class... Ts>
decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};
template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };
namespace utils::dynamic_bitset {
template<typename set_t = int, typename... Ts, typename std::enable_if_t<std::conjunction_v<std::is_same<int, Ts>...>>* = nullptr>
int flip(set_t mask, Ts...arg) { return ((mask ^= (1 << arg)), ...); }
template<typename set_t = int, typename... Ts, typename std::enable_if_t<std::conjunction_v<std::is_same<int, Ts>...>>* = nullptr>
bool test(set_t mask, Ts... arg) { return ((mask & (1 << arg)) && ...); }
template<typename set_t = int, typename T, typename std::enable_if_t<std::conjunction_v<std::is_same<int, T>>>* = nullptr>
int count_upto (set_t mask, T n) { int acc = 0; for (int i = 0; i < n; i++) if ((mask & (1 << i)) > 0) acc++; return acc; };
}
class Solution {
public:
bool judgePoint24(vector<int>& nums) {
using namespace utils::dynamic_bitset;
auto x_op_y = [](double x, double y) -> vector<double> {
vector<double> result = {x + y, x * y, x - y, y - x};
if (std::abs(y) > 1e-5) result.emplace_back(x / y);
if (std::abs(x) > 1e-5) result.emplace_back(y / x);
return result;
};
auto f = rec([&](auto&& f, int mask, optional<double> current = std::nullopt) {
if (count_upto<int>(mask, 4) == 4)
return std::abs(current.value() - 24.0) < 1e-5;
else if (not current and mask != 0)
return false;
else if (not current and mask == 0) {
bool acc = false;
for (int i = 0; i < 4; ++i)
for(int j = i + 1; j < 4; ++j)
for (auto x : x_op_y(nums[i], nums[j]))
acc |= f(flip<int>(mask, i, j), x);
return acc;
}
else if (current) {
bool acc = false;
for (int i = 0; i < 4; ++i)
if (not test<int>(mask, i))
for (const auto next : x_op_y(nums[i], current.value()))
acc |= f(flip<int>(mask, i), next);
if (count_upto(mask, 4) <= 2)
for (int i = 0; i < 4; ++i)
for (int j = i + 1; j < 4; ++j)
if (not test<int>(mask, i) and not test<int>(mask, j))
for (auto x : x_op_y(nums[i], nums[j]))
for (auto y : x_op_y(x, current.value()))
acc |= f(flip<int>(mask, i, j), y);
return acc;
}
throw std::domain_error("unmatched");
});
return f(0);
}
};