package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/can-i-win/
 */
public class Problem464 {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) {
            return true;
        }
        int sum = 0;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            sum += i;
        }
        if (sum < desiredTotal) {
            return false;
        }
        int[] nums = new int[maxChoosableInteger + 1];
        return canIWin(nums, desiredTotal, 0, Player.P2, new HashMap<>()) == Player.P1;
    }

    private enum Player {
        P1, P2
    }

    private static Player canIWin(int[] nums, int desired, int accu, Player player,
                                  Map<String, Player> memo) {
        if (accu >= desired) {
            return player;
        }
        // TODO: the memo isn't optimized
        String key = Arrays.toString(nums);
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        Player win = player;
        for (int num = 1; num < nums.length; num++) {
            if (nums[num] == 1) {
                continue;
            }
            nums[num] = 1;
            Player nextPlayer = (player == Player.P1) ? Player.P2 : Player.P1;
            if (player == Player.P1) {
                win = canIWin(nums, desired, accu + num, nextPlayer, memo);
                if (win == Player.P2) {
                    nums[num] = 0;
                    break;
                }
            } else if (player == Player.P2) {
                win = canIWin(nums, desired, accu + num, nextPlayer, memo);
                if (win == Player.P1) {
                    nums[num] = 0;
                    break;
                }
            }
            nums[num] = 0;
        }
        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
//        System.out.println(prob.canIWin(10, 0)); // true
        System.out.println(prob.canIWin(5, 50)); // true
    }
}

@@ -16,33 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0A
 impo
@@ -489,82 +489,45 @@
     
-int%5B%5D nums = new int%5BmaxChoosableInteger + 1%5D;%0A        return canIWin(nums
+return canIWin(0, maxChoosableInteger
 , de
@@ -551,16 +551,28 @@
 ayer.P2,
+%0A           
  new Has
@@ -691,15 +691,22 @@
 (int
-%5B%5D nums
+ bits, int max
 , in
@@ -729,24 +729,11 @@
 ccu,
- Player player,%0A
+%0A  
     
@@ -764,20 +764,34 @@
     
-  Map%3CString
+Player player, Map%3CInteger
 , Pl
@@ -876,94 +876,8 @@
   %7D%0A
-        // TODO: the memo isn't optimized%0A        String key = Arrays.toString(nums);%0A
     
@@ -901,19 +901,20 @@
 ainsKey(
-key
+bits
 )) %7B%0A   
@@ -938,19 +938,20 @@
 emo.get(
-key
+bits
 );%0A     
@@ -1011,17 +1011,17 @@
 m = 
-1
+0
 ; num %3C 
 nums
@@ -1020,19 +1020,11 @@
 m %3C 
-nums.length
+max
 ; nu
@@ -1050,22 +1050,41 @@
 if (
-nums%5Bnum%5D
+(bits & (1 %3C%3C num))
  == 
-1
+(1 %3C%3C num)
 ) %7B%0A
@@ -1139,21 +1139,24 @@
     
-nums%5Bnum%5D = 1
+bits %7C= 1 %3C%3C num
 ;%0A  
@@ -1293,36 +1293,41 @@
   win = canIWin(
-nums
+bits, max
 , desired, accu 
@@ -1323,32 +1323,36 @@
 ired, accu + num
+ + 1
 , nextPlayer, me
@@ -1412,37 +1412,43 @@
             
-nums%5Bnum%5D = 0
+bits &= ~(1 %3C%3C num)
 ;%0A          
@@ -1558,20 +1558,25 @@
 canIWin(
-nums
+bits, max
 , desire
@@ -1588,16 +1588,20 @@
 cu + num
+ + 1
 , nextPl
@@ -1677,1400 +1677,179 @@
     
-nums%5Bnum%5D = 0;%0A                    break;%0A                %7D%0A            %7D%0A            nums%5Bnum%5D = 0;%0A        %7D%0A        memo.put(key, win);%0A        return win;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem464 prob = new Problem464();%0A//        System.out.println(prob.canIWin(10, 11)); // false%0A//        System.out.println(prob.canIWin(4, 6)); // true%0A//        System.out.println(prob.canIWin(10, 100)); // false%0A//        System.out.println(prob.canIWin(10, 55)); // false%0A//        System.out.println(prob.canIWin(6, 20)); // false%0A//        System.out.println(prob.canIWin(6, 15)); // true%0A//        System.out.println(prob.canIWin(6, 10)); // true%0A//        System.out.println(prob.canIWin(5, 12)); // true%0A//        System.out.println(prob.canIWin(5, 15)); // true%0A//        System.out.println(prob.canIWin(10, 0)); // true%0A//        System.out.println(prob.canIWin(18, 79)); // true%0A//        System.out.println(prob.canIWin(20, 200)); // false%0A//        System.out.println(prob.canIWin(11, 25)); // true%0A//        System.out.println(prob.canIWin(18, 79)); // true%0A//        System.out.println(prob.canIWin(10, 40)); // false%0A//        System.out.println(prob.canIWin(20, 54)); // true%0A//        System.out.println(prob.canIWin(20, 210)); // false%0A//        System.out.println(prob.canIWin(10, 0)); // true%0A        System.out.println(prob.canIWin(5, 50)); // true
+bits &= ~(1 %3C%3C num);%0A                    break;%0A                %7D%0A            %7D%0A            bits &= ~(1 %3C%3C num);%0A        %7D%0A        memo.put(bits, win);%0A        return win;
 %0A   

Solve roblem 464 (finally!)