Facebook Pixel

679. 24 Game

HardArrayMathBacktracking
Leetcode Link

Problem Description

You're given an array of four integers in the range [1, 9], which represent four cards. The objective is to determine whether you can arrange these cards into a mathematical expression that equals 24. This expression should use the standard mathematical operators: addition (+), subtraction (-), multiplication (*), and division (/), as well as parentheses to change the operator precedence if necessary.

The challenge has a few rules:

  • Division is real division, not integer division, which means you should preserve the fractional part of the result (if any).
  • You must use the numbers as they are; you cannot use a number as a unary operator (like negation) or concatenate numbers to form new digits.
  • Each operation must be between two numbers.

Your goal is to return true if such an arrangement is possible that evaluates to 24, otherwise, return false.

Flowchart Walkthrough

First, let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • No: The problem does not involve traditional graphs with nodes and edges depicting relationships or connections.

Need to solve for kth smallest/largest?

  • No: The problem is not about ordering elements or finding a specific element based on its size.

Involves Linked Lists?

  • No: The problem doesn't use linked lists; it primarily deals with numbers and operations on them.

Does the problem have small constraints?

  • Yes: The problem has relatively small constraints given there are only four numbers and basic arithmetic operations.

Brute force / Backtracking?

  • Yes: Brute force or backtracking is suitable as the problem requires exploring various combinations and sequences of operations to achieve the target of 24 from four numbers.

Conclusion: The flowchart suggests using a backtracking approach for trying all possible operations combinations on the given numbers to reach the target value, making the problem suitable for a backtracking pattern.

Intuition

Thinking Process

Given the small size of the problem (four numbers), brute force is a viable strategy. Brute force in this scenario means trying out every possible combination of numbers and operations. Since there are only four numbers and we want to examine every combination of them with every possible operation, we can get all permutations of these numbers and apply different operations between each pair in the permutations.

The problem with typical brute force is that it can sometimes lead to repetitive calculations or it could compute expressions that are not necessarily valid under the given rules. To optimize brute force, we use a recursive function to generate all possible expressions and evaluate them.

Approach

  • First, we convert the array of integers into a list of doubles so that we can handle real division accurately during the calculations.
  • We apply a depth-first search (DFS) approach. This means we'll continually dive into one possibility until we reach the end (which is, in this case, one number remaining in our list), evaluate that, and then backtrack to explore other possibilities.
  • At each step of the recursion, we select two different numbers and perform all possible operations on them. For this, we create a temporary list for each operation—addition, subtraction, multiplication, and both ways of division—as long as the divisor is not zero.
  • After performing an operation, we add the result back into the list and recursively call the DFS function with this new list which is now one element shorter.
  • We keep doing this until we're down to a single element in the list. If at any point the single remaining number in the list is equal to 24 (within a small error margin to account for floating-point imprecision), we've found a valid expression and can thus return true.
  • If none of the combinations result in 24, we return false.

This recursive process allows us to efficiently try out all valid combinations of operations on the given numbers.

Learn more about Math and Backtracking patterns.

Solution Approach

The solution is implemented using a depth-first search (DFS) algorithm. The concept of recursion is key here, as we delve into each possibility in depth first, before backtracking and moving on to other possibilities. Here's how it works in the context of our solution:

Data Structures

The primary data structures used here are:

  • List of Doubles (List<Double>): To facilitate accurate computation of real numbers and allow dynamic removal and addition of elements.
  • Arrays and ArrayList: For handling the data and creating new state lists during the recursive calls.

Algorithm

  1. Conversion: The input integer array cards is converted into a List<Double> so we can perform real number arithmetic and manage dynamic list operations.

  2. Depth-First Search (DFS): The core function dfs() takes a list of numbers and performs the following tasks recursively:

    • Base Cases:

      • Empty list: If the list is empty, it can't make 24, so it returns false.
      • Single element: If the list has one element, we check if it's approximately 24 (within a tolerance to account for floating-point arithmetic errors) and return true or false based on this check.

    • Selection and Operation:

      • We select every possible pair of numbers from the list and perform all valid operations on them. To do this, two nested loops are used to go through each pair uniquely.

    • Recursive Calls:

      • For each pair and operation, we construct a new list that replaces the pair with their operation result and recursively call dfs() on this new list. The getList() method handles this by performing the specified operation and skipping the selected indices.

    • Pruning:

      • During division operations, we check for division by zero and skip creating a new list if it occurs.

  3. Result Combination (Backtracking): As we backtrack, if any recursive call returns true (meaning it found a way to reach 24), we propagate this result back up and ultimately return true. If no recursive path yields 24, we return false.

Breaking down the critical functions:

  • dfs(List<Double> numList): Is the DFS method responsible for exploring all operations and managing the recursion.
  • getList(List<Double> numList, int i, int j, int operate): Is a helper method that creates a new list after performing the operation indicated by operate on elements i and j.

By applying DFS, the code systematically goes through all mathematical expressions that can be formed with the given numbers and operators, checking if any yield the desired result.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say the input array is [4, 1, 8, 7], and we need to check if it's possible to arrange these numbers using the standard operations to get a result of 24.

  1. Conversion to Double:

    • We convert the array into a list of doubles for precise calculations: [4.0, 1.0, 8.0, 7.0].

  2. Depth-First Search (DFS):

    • We initiate our recursive DFS function to explore every possibility.

  3. Select Pairs and Apply Operations:

    • First pair: 4.0 and 1.0.

      • Add: (4.0 + 1.0) → New list: [5.0, 8.0, 7.0].
      • Subtract: (4.0 - 1.0) → New list: [3.0, 8.0, 7.0].
      • Multiply: (4.0 * 1.0) → New list: [4.0, 8.0, 7.0].
      • Divide: (4.0 / 1.0) → New list: [4.0, 8.0, 7.0] (Same as multiplication in this case).

    • Assume the first operation we try is (8.0 * (7.0 - (4.0 - 1.0))), which simplifies to 8.0 * 3.0.

  4. Evaluate Expressions Recursively:

    • We now have a new expression 8.0 * 3.0 to evaluate. We replace the 8.0 and the result of (7.0 - (4.0 - 1.0)) in the list, resulting in [24.0].
    • Since we're left with a single number, the DFS checks if it's approximately 24.
    • It is exactly 24, so there is no need for approximations, and the DFS returns true.

  5. Backtrack if Necessary:

    • If the selected pair and operation did not result in 24, we would have backtracked to try other pairs and operations.
    • In this example, we found the required value on the first full calculation, so there's no need to backtrack.

  6. Conclusion:

    • The recursive exploration finds that [4, 1, 8, 7] can indeed form the expression 8 * (7 - (4 - 1)) = 24.
    • Hence, the function returns true, indicating that it's possible to arrange these cards to get 24.

Through this step-by-step evaluation and backtracking, the solution can determine whether any arrangement of the given numbers with the available operations results in 24. In this example, it successfully did.

Solution Implementation

1from typing import List
2
3class Solution:
4    def judge_point24(self, nums: List[int]) -> bool:
5        """ Entry method to judge whether it's possible to reach the target number 24. """
6        # Convert the input list of integers to a list of floats
7        num_list = [float(num) for num in nums]
8        # Initiate depth-first search to evaluate all possible results
9        return self.dfs(num_list)
10  
11    def dfs(self, num_list: List[float]) -> bool:
12        """ Recursive method to perform depth-first search. """
13        # If there are no numbers, we cannot perform any operations; return False
14        if not num_list:
15            return False
16        # If there is only one number left, check if it's approximately 24
17        if len(num_list) == 1:
18            return abs(num_list[0] - 24.0) < 1e-6
19        # Try all pairs of numbers with all operations
20        for i in range(len(num_list)):
21            for j in range(i+1, len(num_list)):
22                # Perform all operations on the pair (num_list[i], num_list[j])
23                for operation in range(6):
24                    next_list = self.get_next_list(num_list, i, j, operation)
25                    # If successful combination is found, return True
26                    if next_list and self.dfs(next_list):
27                        return True
28        # If no combination resulted in 24, return False
29        return False
30  
31    def get_next_list(self, num_list: List[float], first_index: int, second_index: int, operation: int) -> List[float]:
32        """ Method to create a new list by applying an operation to a pair of numbers. """
33        next_list = [num_list[k] for k in range(len(num_list)) if k != first_index and k != second_index]
34      
35        # Perform the operation based on the operation index
36        if operation == 0: # Addition
37            next_list.append(num_list[first_index] + num_list[second_index])
38        elif operation == 1: # Subtraction (first - second)
39            next_list.append(num_list[first_index] - num_list[second_index])
40        elif operation == 2: # Subtraction (second - first)
41            next_list.append(num_list[second_index] - num_list[first_index])
42        elif operation == 3: # Multiplication
43            next_list.append(num_list[first_index] * num_list[second_index])
44        elif operation == 4: # Division (first / second), check for division by zero
45            if num_list[second_index] != 0:
46                next_list.append(num_list[first_index] / num_list[second_index])
47            else:
48                return []
49        elif operation == 5: # Division (second / first), check for division by zero
50            if num_list[first_index] != 0:
51                next_list.append(num_list[second_index] / num_list[first_index])
52            else:
53                return []
54      
55        # Return the new list to continue the search
56        return next_list
57
1class Solution {
2    // Entry method to judge whether it's possible to reach the target number 24.
3    public boolean judgePoint24(int[] nums) {
4        // Convert the input array of integers to a list of doubles.
5        List<Double> numList = Arrays.stream(nums).boxed().map(Double::new).collect(Collectors.toList());
6        // Initiate depth-first search to evaluate all possible results.
7        return dfs(numList);
8    }
9
10    // Recursive method to perform depth-first search.
11    private boolean dfs(List<Double> numList) {
12        // If there are no numbers, we cannot perform any operations; return false.
13        if (numList.size() == 0) {
14            return false;
15        }
16        // If there is only one number left, check if it's approximately 24.
17        if (numList.size() == 1) {
18            return Math.abs(numList.get(0) - 24.0) < 1e-6;
19        }
20        // Try all pairs of numbers with all operations.
21        for (int i = 0; i < numList.size(); i++) {
22            for (int j = i + 1; j < numList.size(); j++) {
23                // Check if the result of any operation on these two numbers
24                // combined with the remaining numbers can result in 24.
25                for (int operation = 0; operation < 6; operation++) {
26                    List<Double> nextList = getNextList(numList, i, j, operation);
27                    if (!nextList.isEmpty() && dfs(nextList)) {
28                        return true;
29                    }
30                }
31            }
32        }
33        // If no combination resulted in 24, return false.
34        return false;
35    }
36
37    // Method to create a new list by applying an operation to a pair of numbers.
38    private List<Double> getNextList(List<Double> numList, int firstIndex, int secondIndex, int operation) {
39        List<Double> nextNumList = new ArrayList<>();
40        // Add all numbers except the pair we're operating on.
41        for (int k = 0; k < numList.size(); k++) {
42            if (k != firstIndex && k != secondIndex) {
43                nextNumList.add(numList.get(k));
44            }
45        }
46
47        // Perform the operation based on the operation index.
48        switch (operation) {
49            case 0: // Addition
50                nextNumList.add(numList.get(firstIndex) + numList.get(secondIndex));
51                break;
52            case 1: // Subtraction (first - second)
53                nextNumList.add(numList.get(firstIndex) - numList.get(secondIndex));
54                break;
55            case 2: // Subtraction (second - first)
56                nextNumList.add(numList.get(secondIndex) - numList.get(firstIndex));
57                break;
58            case 3: // Multiplication
59                nextNumList.add(numList.get(firstIndex) * numList.get(secondIndex));
60                break;
61            case 4: // Division (first / second), check for division by zero.
62                if (numList.get(secondIndex) == 0) {
63                    return Collections.emptyList();
64                }
65                nextNumList.add(numList.get(firstIndex) / numList.get(secondIndex));
66                break;
67            case 5: // Division (second / first), check for division by zero.
68                if (numList.get(firstIndex) == 0) {
69                    return Collections.emptyList();
70                }
71                nextNumList.add(numList.get(secondIndex) / numList.get(firstIndex));
72                break;
73        }
74
75        // Return the new list of numbers to continue the search.
76        return nextNumList;
77    }
78}
79
1#include <vector>
2#include <cmath>
3#include <algorithm>
4
5class Solution {
6public:
7    // Entry method to judge whether it's possible to reach the target number 24.
8    bool judgePoint24(std::vector<int>& nums) {
9        // Convert the input array of integers to a vector of doubles.
10        std::vector<double> numList(nums.begin(), nums.end());
11        // Initiate depth-first search to evaluate all possible results.
12        return dfs(numList);
13    }
14
15private:
16    // Recursive method to perform depth-first search.
17    bool dfs(std::vector<double>& numList) {
18        // If there are no numbers, we cannot perform any operations; return false.
19        if (numList.empty()) {
20            return false;
21        }
22        // If there is only one number left, check if it's approximately 24.
23        if (numList.size() == 1) {
24            return std::abs(numList[0] - 24.0) < 1e-6;
25        }
26        // Try all pairs of numbers with all operations.
27        for (int i = 0; i < numList.size(); ++i) {
28            for (int j = i + 1; j < numList.size(); ++j) {
29                // Check if the result of any operation on these two numbers
30                // combined with the remaining numbers can result in 24.
31                for (int operation = 0; operation < 6; ++operation) {
32                    std::vector<double> nextList = getNextList(numList, i, j, operation);
33                    if (!nextList.empty() && dfs(nextList)) {
34                        return true;
35                    }
36                }
37            }
38        }
39        // If no combination resulted in 24, return false.
40        return false;
41    }
42
43    // Method to create a new list by applying an operation to a pair of numbers.
44    std::vector<double> getNextList(std::vector<double>& numList, int firstIndex, int secondIndex, int operation) {
45        std::vector<double> nextNumList;
46        // Add all numbers except the pair we're operating on.
47        for (int k = 0; k < numList.size(); ++k) {
48            if (k != firstIndex && k != secondIndex) {
49                nextNumList.push_back(numList[k]);
50            }
51        }
52
53        // Perform the operation based on the operation index.
54        double firstNumber = numList[firstIndex];
55        double secondNumber = numList[secondIndex];
56
57        switch (operation) {
58            case 0: // Addition
59                nextNumList.push_back(firstNumber + secondNumber);
60                break;
61            case 1: // Subtraction (first - second)
62                nextNumList.push_back(firstNumber - secondNumber);
63                break;
64            case 2: // Subtraction (second - first)
65                nextNumList.push_back(secondNumber - firstNumber);
66                break;
67            case 3: // Multiplication
68                nextNumList.push_back(firstNumber * secondNumber);
69                break;
70            case 4: // Division (first / second), check for division by zero.
71                if (std::abs(secondNumber) < 1e-6) {
72                    return {};
73                }
74                nextNumList.push_back(firstNumber / secondNumber);
75                break;
76            case 5: // Division (second / first), check for division by zero.
77                if (std::abs(firstNumber) < 1e-6) {
78                    return {};
79                }
80                nextNumList.push_back(secondNumber / firstNumber);
81                break;
82        }
83
84        // Return the new list of numbers to continue the search.
85        return nextNumList;
86    }
87};
88
1// Entry function to judge whether it's possible to reach the target number 24.
2function judgePoint24(nums: number[]): boolean {
3    // Convert the input array of numbers to an array of doubles (in JS/TS, all numbers are floating point).
4    const numList: number[] = nums.map(num => num);
5    // Initiate depth-first search to evaluate all possible results.
6    return dfs(numList);
7}
8
9// Recursive function to perform depth-first search.
10function dfs(numList: number[]): boolean {
11    // If there are no numbers, we cannot perform any operations; return false.
12    if (numList.length === 0) {
13        return false;
14    }
15    // If there is only one number left, check if it's approximately 24.
16    if (numList.length === 1) {
17        return Math.abs(numList[0] - 24) < 1e-6;
18    }
19    // Try all pairs of numbers with all operations.
20    for (let i = 0; i < numList.length; i++) {
21        for (let j = i + 1; j < numList.length; j++) {
22            // Check if the result of any operation on these two numbers
23            // combined with the remaining numbers can result in 24.
24            for (let operation = 0; operation < 6; operation++) {
25                const nextList = getNextList(numList, i, j, operation);
26                if (nextList.length > 0 && dfs(nextList)) {
27                    return true;
28                }
29            }
30        }
31    }
32    // If no combination resulted in 24, return false.
33    return false;
34}
35
36// Function to create a new list by applying an operation to a pair of numbers.
37function getNextList(numList: number[], firstIndex: number, secondIndex: number, operation: number): number[] {
38    let nextNumList: number[] = [];
39    // Add all numbers except the pair we're operating on.
40    for (let k = 0; k < numList.length; k++) {
41        if (k !== firstIndex && k !== secondIndex) {
42            nextNumList.push(numList[k]);
43        }
44    }
45
46    // Perform the operation based on the operation index.
47    switch (operation) {
48        case 0: // Addition
49            nextNumList.push(numList[firstIndex] + numList[secondIndex]);
50            break;
51        case 1: // Subtraction (first - second)
52            nextNumList.push(numList[firstIndex] - numList[secondIndex]);
53            break;
54        case 2: // Subtraction (second - first)
55            nextNumList.push(numList[secondIndex] - numList[firstIndex]);
56            break;
57        case 3: // Multiplication
58            nextNumList.push(numList[firstIndex] * numList[secondIndex]);
59            break;
60        case 4: // Division (first / second), ensure no division by zero.
61            if (numList[secondIndex] !== 0) {
62                nextNumList.push(numList[firstIndex] / numList[secondIndex]);
63            } else { // If division by zero would occur, return an empty list.
64                return [];
65            }
66            break;
67        case 5: // Division (second / first), ensure no division by zero.
68            if (numList[firstIndex] !== 0) {
69                nextNumList.push(numList[secondIndex] / numList[firstIndex]);
70            } else { // If division by zero would occur, return an empty list.
71                return [];
72            }
73            break;
74    }
75
76    // Return the new list of numbers to continue the search.
77    return nextNumList;
78}
79

Time and Space Complexity

Time Complexity

The given solution uses a depth-first search (DFS) strategy that explores all possible ways to combine the input numbers using the four mathematical operations (addition, subtraction, multiplication, division) to achieve the target number 24.

At every recursive step, the algorithm iterates through all pairs of numbers available in the numList. For each pair of numbers, there are 6 different possibilities to explore (since it tries both a+b and b-a, a*b and b/a etc., including order). The number of possibilities to evaluate decreases after each operation because one number is taken out of the list, and a new number (result of the operation) is inserted back into the list.

The time complexity of DFS depends on the branching factor (average number of successors per state) and the maximum depth of recursion.

Here’s a breakdown:

  • The algorithm starts with 4 numbers and computes the result of merging any two numbers into one by one of 6 operations. This leads to a branching factor of C(4,2)*6 = 6*6, where C(n,k) denotes a combination of n items taken k at a time.
  • The next recursive call has 3 numbers and possible pairings are C(3,2)*6 = 3*6.
  • The last one has 2 numbers left and just C(2,2)*6 = 1*6.

The maximum depth of recursion would be 3 since it takes 3 operations to reduce the original list of 4 numbers to a single number.

Combining these observations, the time complexity is O((6*6) * (3*6) * (1*6)) = O(6^4) = O(1296).

Space Complexity

Space complexity consists of the space used to store the numList copy at each recursive call stack, and the space needed for the stack itself due to recursion.

  • The maximum depth of recursive calls is 3, so there will be at most 3 active calls on the call stack at any time.
  • Each call has its own copy of the list, which decreases in size by one at each level. The space taken by lists is O(4 + 3 + 2) as we remove elements gradually.

So, the space complexity is O(4), as the list space usage is constant and does not grow with the input, and the maximum depth of the recursive call stack is also a constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More