Space
Open
From Fieldwork
Scales
Archive
Parentheses simply denote order, so we can just try everything. We iterate through every possible pair at every stage.
Time Complexity Analysis
At first glance, this looks expensive, but for N=4, it is very small. This is technically O(1) because the input size is fixed, but let's derive the generalized complexity to show the interviewer we know our math.
We have 3 stages of recursion for 4 numbers.
Stage 1: 4 numbers left
We choose an ordered pair of numbers (i, j).
There are 4 choices for i and 3 choices for j (since i≠j).
Total pairs: 4×3=12 pairs.
For each pair, we run 4 operations (+, -, *, /).
Total branches: 12×4=48.
Stage 2: 3 numbers left
We passed 1 result + 2 existing numbers = 3 numbers.
We choose an ordered pair.3×2=6 pairs.
4 operations.
Total branches: 6×4=24.
Stage 3: 2 numbers left
We passed 1 result + 1 existing number = 2 numbers.
We choose an ordered pair. 2×1=2 pairs.
4 operations.
Total branches:
2×4=8
Total Operations (Upper Bound):
48×24×8=9,216
We perform roughly 9,216 recursive calls in the worst case (if we find no solution).
For a computer, 9,000 operations is instantaneous.
Note: The actual number is slightly lower because we don't divide by zero, and we stop as soon as we find True.
https://aistudio.google.com/prompts/1QfU4hBSamwdtDapaQjDvDeQZA-smhQ8w
class Solution:
def judgePoint24(self, cards: List[int]) -> bool:
# Use a small epsilon for float comparison
EPSILON = 1e-6
def backtrack(nums):
# Base Case: If only one number remains, check if it's 24
if len(nums) == 1:
return abs(nums[0] - 24) < EPSILON
# Try picking every possible pair of numbers (i, j)
for i in range(len(nums)):
for j in range(len(nums)):
# Must pick two different cards
if i == j:
continue
# Create a list of the numbers NOT picked
next_nums = []
for k in range(len(nums)):
if k != i and k != j:
next_nums.append(nums[k])
# We will try all operations on nums[i] and nums[j]
# and append the result to next_nums
val1 = nums[i]
val2 = nums[j]
# Possible results from operations
# Note: For + and *, order doesn't matter, but our loop
# tries (i,j) and (j,i), so we technically compute it twice.
# That is fine for n=4.
# 1. Addition
next_nums.append(val1 + val2)
if backtrack(next_nums): return True
next_nums.pop() # Backtrack
# 2. Multiplication
next_nums.append(val1 * val2)
if backtrack(next_nums): return True
next_nums.pop()
# 3. Subtraction (val1 - val2)
# The loop will eventually swap i and j to cover (val2 - val1)
next_nums.append(val1 - val2)
if backtrack(next_nums): return True
next_nums.pop()
# 4. Division (val1 / val2)
if abs(val2) > EPSILON: # Avoid division by zero
next_nums.append(val1 / val2)
if backtrack(next_nums): return True
next_nums.pop()
return False
return backtrack(cards)Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode