679. 24 Game

Description

image-20210811232640270

Solution

Recursively check all the potential combination of the 4 numbers. In each round, we iteratively select 2 out of N numbers, calculate the result of +, -, *, / then put back the result into next round.

Don’t forget the function return condition is if N == 1, nums[0] == 24 . And for float number, we should do this in abs() < 1e-6

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    int op[4] = {1,2,3,4};
public:
    bool judgePoint24(vector<int>& cards) {
        vector<double> nums;
        for(auto card : cards)
            nums.push_back(1.0 * card);
        return dfs(nums);
    }

    bool dfs(vector<double>& nums){
        int n = nums.size();
        if(n == 1)
            return (abs(nums[0] - 24) < 1e-6);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j)
                    continue;
                double a = nums[i], b = nums[j];
                vector<double> newnums;
                for(int k = 0; k < n; k++)
                    if(k != i && k != j)
                        newnums.push_back(nums[k]);
                
                newnums.push_back(-1);
                //iterate all operators
                newnums.back() = a + b;
                if(dfs(newnums)) return true;

                newnums.back() = a - b;
                if(dfs(newnums)) return true;

                newnums.back() = a * b;
                if(dfs(newnums)) return true;

                if(b != 0){
                    newnums.back() = a / b;
                    if(dfs(newnums)) return true;
                }
            }
        }
        return false;
    }
};

679-2