Sponsored
Sponsored
This approach uses recursion and backtracking to try every possible permutation of the cards array and examines all the possible binary operations on them. The goal is to see if there is any combination that can evaluate to 24.
We recursively solve smaller expressions, trying each of the four operations in each step on each pair of elements. Since we can use parentheses, we essentially try to evaluate each pair first and reduce it to a smaller problem with one less number.
To handle permutations, we can make use of a generator that produces all permutations of the numbers.
Time Complexity: O(1), because even though there are a large number of potential permutations (4! = 24), the constant nature of 4 elements leads to a constant time complexity.
Space Complexity: O(1), as we reuse input space without additional data structures beyond call stack recursion.
1import itertools
2
3def calculate(a, b):
4 return [a + b, a - b, b - a, a * b, a / b if b != 0 else float('inf'), b / a if a != 0 else float('inf')]
5
6def solve(cards):
7 if len(cards) == 1:
8 return abs(cards[0] - 24) < 1e-6
9 for a, b, *rest in itertools.permutations(cards, 4):
10 for result in calculate(a, b):
11 if solve([result] + rest):
12 return True
13 return False
14
15cards = [4, 1, 8, 7]
16print(solve(cards)) # Output: TrueThe Python solution defines a helper function calculate that takes two numbers and returns a list of results from all possible operations on them. We then use permutations of the integers in cards and apply the operations recursively. The function returns True if any combination of operations results in the number 24.
Instead of using recursion, we can store intermediate results in a set to track states as we iteratively combine cards using operations. This simulates reducing the problem by iteratively solving and eliminating possibilities that cannot possibly lead to 24.
For each unique combination of card values reduced by each operation, continue until the desired result is achieved or possibilities are exhausted.
Time Complexity: O(1), bounded by 4 elements and evaluation paths.
Space Complexity: O(1), not exceeding static set sizes for temporary card space.
1#include <stdio.h>
2#include <stdlib.h>
3
This C solution mimics the recursive logic in a manner akin to iterative through self-contained nested function calls using index-based state tracking. Adjustments are made in-place with result comparisons continuing permutated evaluations of the cards, swapping back after trials.