Twenty Four Game(24 Game)

This page explains Java solution to problem Twenty Four Game(24 Game) using Backtracking.

Problem Statement

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class TwentyFourGame {
    boolean res = false;
    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        for(int num: nums) list.add((double)num);
        helper(list);
        return res;
    }

    private void helper(List<Double> list) {
        if(res) return;
        if(list.size() == 1) {
            if(Math.abs(24 - list.get(0)) < 1e-5) res = true;
        }
        else {
            for(int i = 1; i < list.size(); i++) {
                for(int j = 0; j < i; j++) {
                    double d1 = list.get(i);
                    double d2 = list.get(j);
                    List<Double> possibilities = possibilities(d1, d2);

                    list.remove(i);
                    list.remove(j);
                    for(Double d: possibilities) {
                        list.add(d);
                        helper(list);
                        list.remove(list.size() - 1);
                    }
                    list.add(j, d2);
                    list.add(i, d1);
                }
            }
        }
    }

    private List<Double> possibilities(double d1, double d2) {
        List<Double> list = new ArrayList<>();
        list.add(d1 + d2);
        list.add(d1 - d2);
        list.add(d2 - d1);
        list.add(d1 * d2);
        if(d2 != 0) list.add(d1 / d2);
        if(d1 != 0) list.add(d2 / d1);
        return list;
    }
}

Time Complexity

O(1)
Max number of cards are always going to be 4

Space Complexity

O(1)