Fork me on GitHub

Can I Win

Posted on

Description

https://leetcode.com/problems/can-i-win/description/

Solution

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 {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger * (1 + maxChoosableInteger) < desiredTotal) return false;
        vector<char> states(1<<maxChoosableInteger, 0);
        helper(desiredTotal, states, 0, 1, maxChoosableInteger);
        return states[0] == 1;
    }
    
    void helper(int target, vector<char>& states, int currentState, int currentUser, int count) {
        if (states[currentState] != 0) return;
        
        for (int i = 0; i < count; ++i) {
            if (currentState & (1<<i)) continue; //Skip it when the number is taken.
            if ((i + 1) >= target) {states[currentState] = currentUser; return;} //Satisfy;
            helper(target - (i + 1), states, currentState | (1<<i), -currentUser, count);
            if (states[currentState | (1<<i)] == currentUser) {
                states[currentState] = currentUser;
                return;
            }
        }
        
        states[currentState] = -currentUser;
        return;
    }
};