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.
1function operations(a, b) {
2 return [a + b, a - b, b - a, a * b, a / b, b / a];
3}
4
5function canMake24(cards) {
6 if (cards.length === 1) return Math.abs(cards[0] - 24) < 1e-6;
7 for (let i = 0; i < cards.length; i++) {
8 for (let j = 0; j < cards.length; j++) {
9 if (i !== j) {
10 const rest = cards.filter((_, index) => index !== i && index !== j);
11 for (const op of operations(cards[i], cards[j])) {
12 if (canMake24([op, ...rest])) return true;
13 }
14 }
15 }
16 }
17 return false;
18}
19
20let cards = [4, 1, 8, 7];
21console.log(canMake24(cards)); // Output: trueThis JavaScript solution similarly uses recursion to try all permutations of card pairs and all operations to determine if the expression evaluates to 24. It filters remaining numbers after selecting two, computes all operation results of these two, and proceeds with recursion.
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.