Backtracking beats 95.29% [Java]
Apparently, there are limited number of combinations for cards and operators (+-*/()). One idea is to search among all the possible combinations. This is what b
Apparently, there are limited number of combinations for cards and operators (``+-*/()``). One idea is to search among all the possible combinations. This is what backtracking does.\n\nNote that ``()`` play no role in this question. Say, parentheses give some operators a higher priority to be computed. However, the following algorithm has already considered priorities, thus it's of no use to take parentheses into account anymore.\n\n``arr`` contains value for cards and ``vis[i]`` indicates whether ``arr[i]`` has been used or not. Every time select 2 un-used cards ``arr[i]`` and ``arr[j]``. Calculate the answer for ``arr[i]`` and ``arr[j]`` with some operator, update ``arr[i]`` with this new value and mark ``arr[j]`` as visited. Now we have 1 less card available. Note that we should use that new value (new ``arr[i]``) in the future, thus we should NOT mark ``arr[i]`` as visited. When there is no card available, check whether the answer is 24 or not.\n\nSince each time after we select 2 cards ``arr[i]`` and ``arr[j]``, we just do the calculation without considering the priorities for operators we use, we could think that we have already added a pair of ``()`` for ``arr[i] OPERATOR arr[j]``. This contains all the possible considerations, thus we do not need to consider parentheses anymore.\n\n```\npublic boolean judgePoint24(int[] nums) {\n        boolean[] vis = new boolean[4];\n        double[] arr = new double[4];\n        for (int i=0; i<4; i++) arr[i] = 1.0 * nums[i];\n        return f(arr, vis, 4);\n    }\n    \n    boolean f(double[] arr, boolean[] vis, int available) {\n        double prev = 0;\n        if (available==1) {\n            for (int i=0; i<arr.length; i++) \n                if (!vis[i]) return Math.abs(arr[i]-24)<0.000001?true:false;\n        } \n        for (int i=0; i<arr.length; i++) {\n            if (vis[i]) continue;\n            // prev is for backtracking\n            prev = arr[i];\n            for (int j=i+1; j<arr.length; j++) {\n                // calculate i & j\n                if (vis[j]) continue;\n                vis[j] = true;\n                \n                // add\n                arr[i] = prev + arr[j];\n                if (f(arr, vis, available-1)) return true;\n                \n                // minus\n                arr[i] = prev - arr[j];\n                if (f(arr, vis, available-1)) return true;\n                arr[i] = -prev + arr[j];\n                if (f(arr, vis, available-1)) return true;\n                \n                // multiply\n                arr[i] = prev * arr[j];\n                if (f(arr, vis, available-1)) return true;\n                \n                // division\n                arr[i] = prev / arr[j];\n                if (f(arr, vis, available-1)) return true;\n                arr[i] = arr[j] / prev;\n                if (f(arr, vis, available-1)) return true;\n                \n                vis[j] = false;\n            }\n            arr[i] = prev;\n        }\n        return false;\n    }\n```
[]