Skip to content

679. 24 Game 👍

  • Time: $O(2^n)$, where n = 4
  • Space: $O(2^n)$
 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
class Solution {
 public:
  bool judgePoint24(vector<int>& nums) {
    vector<double> doubleNums;

    for (const int num : nums)
      doubleNums.push_back(num);

    return dfs(doubleNums);
  }

 private:
  bool dfs(vector<double>& nums) {
    if (nums.size() == 1)
      return abs(nums[0] - 24) < 0.001;

    for (int i = 0; i < nums.size(); ++i)
      for (int j = 0; j < i; ++j) {
        for (const double num : generate(nums[i], nums[j])) {
          vector<double> nextRound{num};
          for (int k = 0; k < nums.size(); ++k) {
            if (k == i || k == j)  // It is used in `generate()`.
              continue;
            nextRound.push_back(nums[k]);
          }
          if (dfs(nextRound))
            return true;
        }
      }

    return false;
  }

  vector<double> generate(double a, double b) {
    return {a * b, a / b, b / a, a + b, a - b, b - a};
  }
};

 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
class Solution {
  public boolean judgePoint24(int[] nums) {
    List<Double> doubleNums = new ArrayList<>();

    for (final int num : nums)
      doubleNums.add((double) num);

    return dfs(doubleNums);
  }

  private boolean dfs(List<Double> nums) {
    if (nums.size() == 1)
      return Math.abs(nums.get(0) - 24.0) < 0.001;

    for (int i = 0; i < nums.size(); ++i)
      for (int j = i + 1; j < nums.size(); ++j)
        for (final double num : generate(nums.get(i), nums.get(j))) {
          List<Double> nextRound = new ArrayList<>(List.of(num));
          for (int k = 0; k < nums.size(); ++k) {
            if (k == i || k == j) // It is used in `generate()`.
              continue;
            nextRound.add(nums.get(k));
          }
          if (dfs(nextRound))
            return true;
        }

    return false;
  }

  private double[] generate(double a, double b) {
    return new double[] {a * b, a / b, b / a, a + b, a - b, b - a};
  }
}

 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
class Solution:
  def judgePoint24(self, nums: list[int]) -> bool:
    def generate(a: float, b: float) -> list[float]:
      return [a * b,
              math.inf if b == 0 else a / b,
              math.inf if a == 0 else b / a,
              a + b, a - b, b - a]

    def dfs(nums: list[float]) -> bool:
      if len(nums) == 1:
        return abs(nums[0] - 24.0) < 0.001

      for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
          for num in generate(nums[i], nums[j]):
            nextRound = [num]
            for k in range(len(nums)):
              if k == i or k == j:
                continue
              nextRound.append(nums[k])
            if dfs(nextRound):
              return True

      return False

    return dfs(nums)