LeetCode Entry
679. 24 Game
Can a,b,c,d = 24 with ops /+-()
679. 24 Game hard blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1085
Problem TLDR
Can a,b,c,d = 24 with ops */+-() #hard #backtracking #math
Intuition
Solved not optimally.
// 1..9
// ()+-/*
// 12 * 2
// 8 * 3
// 6 * 4
// 2 * 3 * 4
// 2 * 3 * 2 * 2
// 1 - 2/3 = 1/3; 8 / (1 - 2/3)
// 1 - 3/4 = 1/4; 6 / (1 - 3/4)
// 1 - 5/6 = 1/6; 4 / (1 - 5/6)
// 1 - 7/8 = 1/8; 3 / (1 - 7/8)
// 20+4; 5*4+2+2 2+2=1..3 + 3..1
// 5*(2+2)+4
// 21+3; too many to list them all
// implement eval?
// 1 3 4 6
// 6/(1-3/4)
// i don't think my solution is the expected
// 0123456789012
// .x..x...x..x. 13 positions
// ( ( (
// ) ) )
// + + +
// - - -
// * * *
// / / /
// a a a a
// b b b b
// c c c c
// d d d d
My intuition was just to build all possible equations, then parse them and eval.
The optimal intuition (not mine): every equation has the first step than you can do, just compute by picking any two numbers.
Approach
- solve not optimally to appreciate the cleverness of an idea
Complexity
-
Time complexity: \(O(n^(2n))\), n levels deep, n^2 at each level
-
Space complexity: \(O(n^n)\), n levels, n size at each level
Code
// 80ms
fun judgePoint24(cards: IntArray): Boolean {
fun dfs(cs: List<Double>): Boolean {
for (i in cs.indices) for (j in cs.indices) if (i != j) {
val a = cs[i]; val b = cs[j]
val next = arrayListOf(a+b, a-b,b-a, a*b); if(b!=0.0) next += a/b
val rest = (cs.indices - i - j).map {cs[it]}
for (x in next) if (dfs(rest + x)) return true
}
return cs.size == 1 && abs(24.0-cs[0])<0.001
}
return dfs(cards.map { 1.0 * it })
}