679. 24 Game

📝 Problem Details

• Title: 679. 24 Game
• Link: https://leetcode.com/problems/24-game/
• Difficulty: Hard
• Tags/Categories: Backtracking Math Arrays

💭What Were My Initial Thoughts?

brute force approach:
- generate all permutations of the four numbers
- try all possible combinations of operation (+,-,*,/) between them 
- this would  be exponential in time complexity (not very efficient)

- could implement pruning to remove redundant calculations

🤔What Did I Struggle With?

- was unsure how to implement backtracking 

💡 Explanation of Solution

1. Input
	- four numbers
	- operations : +, -, *, /

2. Base Case:
	- if there is only one number left, check if it approximately equal to 24. If so, then return true

3. Recursive Step:
	- select two numbers from the list
	- apply each operation (+, -, *, /) to them
	- replace the two numbers with the result and recurse on the reduced list

4. Backtracking:
	- undo the operatoin and try another pair/operation
	- continue until all possibilities are exhausted 

5. Pruning:
	- skip division by zero
	- skip redundant cases, such as swapping the order of identical (e.g. 3+5 and 5+3)

6. Result:
	- if any recursive path leads to 24, return true
	- if no path, returns false

⌛ Complexity Analysis

Time Complexity:
O(k^2)

Space Complexity:
O(n^2)

💻 Implementation of Solution

 
const double EPSILON = 1e-6; // Tolerance for comparing floating-point numbers
 
// Helper function to check if a number is close to 24
bool isCloseTo24(double num) {
    return fabs(num - 24) < EPSILON;
}
 
// Recursive function to evaluate all possible combinations
bool evaluate(vector<double>& nums) {
    // Base case: If only one number is left, check if it is approximately 24
    if (nums.size() == 1) {
        return isCloseTo24(nums[0]);
    }
 
    // Iterate over all pairs of numbers
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.size(); j++) {
            if (i == j) continue; // Avoid using the same number twice
 
            // Create a new list of numbers by removing nums[i] and nums[j]
            vector<double> nextNums;
            for (int k = 0; k < nums.size(); k++) {
                if (k != i && k != j) nextNums.push_back(nums[k]);
            }
 
            // Try all operations between nums[i] and nums[j]
            vector<double> results = {
                nums[i] + nums[j],
                nums[i] - nums[j],
                nums[i] * nums[j]
            };
 
            // Handle division separately to avoid division by zero
            if (fabs(nums[j]) > EPSILON) {
                results.push_back(nums[i] / nums[j]);
            }
 
            // Recurse for each result
            for (double result : results) {
                nextNums.push_back(result);
                if (evaluate(nextNums)) return true; // Found a solution
                nextNums.pop_back(); // Backtrack
            }
        }
    }
    return false; // No solution found
}
 
bool judgePoint24(vector<int>& cards) {
    // Convert integer cards to double for floating-point calculations
    vector<double> nums(cards.begin(), cards.end());
    return evaluate(nums);
}