package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * https://leetcode.com/problems/can-i-win/
 */
public class Problem464 {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        Set<Integer> nums = new HashSet<>();
        for (int i = 1; i <= maxChoosableInteger; i++) {
            nums.add(i);
        }
        Set<Integer> newNums = new HashSet<>(nums);
        for (int num : nums) {
            newNums.remove(num);
            Map<String, Player> memo = new HashMap<>();
            Player win = canIWin(newNums, desiredTotal, num, Player.P1, memo);
            if (win == Player.P1) {
                return true;
            }
            newNums.add(num);
        }
        return false;
    }

    private enum Player {
        P1, P2
    }

    private static Player canIWin(Set<Integer> nums, int desired, int accu, Player player,
                                  Map<String, Player> memo) {
        if (accu >= desired) {
            return player;
        }
        // TODO: the memo isn't optimized
        String key = nums.toString();
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        Set<Integer> newNums = new HashSet<>(nums);
        Player win = player;
        for (int num : nums) {
            newNums.remove(num);
            Player nextPlayer = (player == Player.P1) ? Player.P2 : Player.P1;
            if (player == Player.P1) {
                win = canIWin(newNums, desired, accu + num, nextPlayer, memo);
                if (win == Player.P2) {
                    break;
                }
            } else if (player == Player.P2) {
                win = canIWin(newNums, desired, accu + num, nextPlayer, memo);
                if (win == Player.P1) {
                    break;
                }
            }
            newNums.add(num);
        }
        memo.put(key, win);
        return win;
    }

    public static void main(String[] args) {
        Problem464 prob = new Problem464();
        System.out.println(prob.canIWin(10, 11)); // false
        System.out.println(prob.canIWin(4, 6)); // true
        System.out.println(prob.canIWin(10, 100)); // false
        System.out.println(prob.canIWin(10, 55)); // false
        System.out.println(prob.canIWin(6, 20)); // false
        System.out.println(prob.canIWin(6, 15)); // true
        System.out.println(prob.canIWin(6, 10)); // true
        System.out.println(prob.canIWin(5, 12)); // true
        System.out.println(prob.canIWin(5, 15)); // true
        System.out.println(prob.canIWin(10, 0)); // true
        System.out.println(prob.canIWin(18, 79)); // true
        System.out.println(prob.canIWin(20, 200)); // false
        System.out.println(prob.canIWin(11, 25)); // true
        System.out.println(prob.canIWin(18, 79)); // true
        System.out.println(prob.canIWin(10, 40)); // false
        System.out.println(prob.canIWin(20, 54)); // true
        System.out.println(prob.canIWin(20, 210)); // false
    }
}

@@ -388,32 +388,54 @@
 d(i);%0A        %7D%0A
+        int bits = 0;%0A
         Set%3CInte
@@ -542,34 +542,65 @@
             
-Map%3CString
+bits %7C= 1 %3C%3C num;%0A            Map%3CInteger
 , Player%3E me
@@ -693,24 +693,30 @@
 yer.P1, memo
+, bits
 );%0A         
@@ -807,32 +807,65 @@
 wNums.add(num);%0A
+            bits &= ~(1 %3C%3C num);%0A
         %7D%0A      
@@ -1064,22 +1064,23 @@
     Map%3C
-String
+Integer
 , Player
@@ -1085,16 +1085,26 @@
 er%3E memo
+, int bits
 ) %7B%0A    
@@ -1213,46 +1213,8 @@
 zed%0A
-        String key = nums.toString();%0A
     
@@ -1238,19 +1238,20 @@
 ainsKey(
-key
+bits
 )) %7B%0A   
@@ -1275,19 +1275,20 @@
 emo.get(
-key
+bits
 );%0A     
@@ -1336,32 +1336,60 @@
 ashSet%3C%3E(nums);%0A
+        int newBits = bits;%0A
         Player w
@@ -1457,32 +1457,65 @@
 ms.remove(num);%0A
+            newBits %7C= 1 %3C%3C num;%0A
             Play
@@ -1684,32 +1684,41 @@
 nextPlayer, memo
+, newBits
 );%0A             
@@ -1911,16 +1911,25 @@
 er, memo
+, newBits
 );%0A     
@@ -2044,32 +2044,68 @@
 wNums.add(num);%0A
+            newBits &= ~(1 %3C%3C num);%0A
         %7D%0A      
@@ -2119,11 +2119,12 @@
 put(
-key
+bits
 , wi

Update problem 464