## 24 Game

• Time:O(2^n), where n = 4
• Space:O(2^n)

## C++

``````class Solution {
public:
bool judgePoint24(vector<int>& nums) {
vector<double> doubleNums;

for (const int num : nums)
doubleNums.push_back(num);

return dfs(doubleNums);
}

private:
bool dfs(vector<double>& nums) {
if (nums.size() == 1)
return abs(nums[0] - 24) < 0.001;

for (int i = 0; i < nums.size(); ++i)
for (int j = 0; j < i; ++j) {
for (const double num : generate(nums[i], nums[j])) {
vector<double> nextRound{num};
for (int k = 0; k < nums.size(); ++k) {
if (k == i || k == j)  // used in generate()
continue;
nextRound.push_back(nums[k]);
}
if (dfs(nextRound))
return true;
}
}

return false;
}

vector<double> generate(double a, double b) {
return {a * b, a / b, b / a, a + b, a - b, b - a};
}
};
``````

## JAVA

``````class Solution {
public boolean judgePoint24(int[] nums) {
List<Double> doubleNums = new ArrayList<>();

for (final int num : nums)

return dfs(doubleNums);
}

private boolean dfs(List<Double> nums) {
if (nums.size() == 1)
return Math.abs(nums.get(0) - 24.0) < 0.001;

for (int i = 0; i < nums.size(); ++i)
for (int j = i + 1; j < nums.size(); ++j)
for (final double num : generate(nums.get(i), nums.get(j))) {
List<Double> nextRound = new ArrayList<>(Arrays.asList(num));
for (int k = 0; k < nums.size(); ++k) {
if (k == i || k == j) // used in generate()
continue;
}
if (dfs(nextRound))
return true;
}

return false;
}

private double[] generate(double a, double b) {
return new double[] {a * b, a / b, b / a, a + b, a - b, b - a};
}
}
``````

## Python

``````class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
def generate(a: float, b: float) -> List[float]:
return [a * b,
math.inf if b == 0 else a / b,
math.inf if a == 0 else b / a,
a + b, a - b, b - a]

def dfs(nums: List[float]) -> bool:
if len(nums) == 1:
return abs(nums[0] - 24.0) < 0.001

for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for num in generate(nums[i], nums[j]):
nextRound = [num]
for k in range(len(nums)):
if k == i or k == j:
continue
nextRound.append(nums[k])
if dfs(nextRound):
return True

return False

return dfs(nums)
``````