Golang/112ms/Recursive-with-cache


  • 1
    N

    Very similar to https://discuss.leetcode.com/topic/69330/quick-c-dp-solution-with-bit-maniplutaion-only-49ms

    func verify(available uint, n, total uint, cache map[uint]bool) (success bool) {
    	if s, found := cache[available]; found {
    		return s
    	}
    	for i := uint(1); i <= n && !success; i++ {
    		if (available & (1 << i)) > 0 {
        		success = total <= i || !verify(available &^ (1 << i), n, total-i, cache)
    		}
    	}
    	cache[available] = success
    	return
    }
    
    func canIWin(n int, total int) bool {
    	available := (uint(1) << uint(n+1)) - 1
    	return (n*(n+1)/2 > total) && verify(available, uint(n), uint(total), make(map[uint]bool))
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.