24 Game - Leetcode Solution

Problem:

Given four integers, your task is to find whether you can construct an arithmetic expression using the four numbers and the operators +, -, *, / such that the value of the expression is 24. You are allowed to use parentheses to group numbers and operations.

Example 1:

Input: [4, 1, 8, 7] Output: True Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2] Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.

2. Every operation is of equal precedence, which means you should evaluate multiplication and division first, and then addition and subtraction.

3. You cannot concatenate numbers together. For example, if the input is [1, 2, 3, 4], you cannot form the number 1234.

Solution:

To solve this problem, we can use a recursive backtracking algorithm to generate all possible arithmetic expressions using the given four numbers and operators. We can keep track of the current expression and its value during the backtracking process, and check whether the value is equal to 24 when the expression is fully generated.

Here are the steps of the algorithm:

1. Define a recursive function backtrack(expression, value, nums) which takes three parameters: expression (string) – the current arithmetic expression, value (float) – the value of the current expression, and nums (list) – the remaining numbers that can be used to generate the expression.

2. If nums is empty and value is equal to 24, we return True since we have found a solution. Otherwise, we return False.

3. For each number x in nums, we remove x from the list and generate four possible expressions using x and the current value: value+x, value-x, value*x, and value/x (if x is not zero). We then call the backtrack function recursively with updated expression, value, and nums. If any of the recursive calls returns True, we return True.

4. If none of the expressions generated in step 3 leads to a solution, we add x back to nums and continue to the next number.

5. If we have tried all possible numbers in nums and none of them leads to a solution, we return False.

Here is the Python implementation of the algorithm:

class Solution: def judgePoint24(self, nums: List[int]) -> bool: def backtrack(expression, value, nums): if not nums: return abs(value - 24) < 1e-6 for i, x in enumerate(nums): new_nums = nums[:i] + nums[i+1:] if backtrack(expression + "+" + str(x), value + x, new_nums): return True if backtrack(expression + "-" + str(x), value - x, new_nums): return True if backtrack(expression + "*" + str(x), value * x, new_nums): return True if x != 0 and backtrack(expression + "/" + str(x), value / x, new_nums): return True return False

    return backtrack("", 0, nums)

Time Complexity:

The worst case time complexity of the algorithm is O(4^n), where n is the number of integers in the given array. This is because we have at most 4 choices (operator +, -, *, /) for each number, and there are n numbers in the expression.

Space Complexity:

The worst case space complexity of the algorithm is O(n), where n is the number of integers in the given array. This is because we need to store the current expression and value during the backtracking process.

1