464. Can I Win

二刷
Version #2 Bit Manipulation

题目条件maxChoosableInteger will not be larger than 20
所以可以用一个int表示所有visited的情况

62.20 %
class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        int visited = 0;
        // If number a is used, set bit a of visited = 1;
        Map<Integer, Boolean> map = new HashMap<>();
        return helper(maxChoosableInteger, desiredTotal, visited, map);   
    }
   
    private boolean helper(int maxChoosableInteger, int desiredTotal, int visited, Map<Integer, Boolean> map) {
        boolean flag = false;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (!isUsed(visited, i)) {
                if (i >= desiredTotal) {
                    flag = true;
                    break;
                }
                int currVisited = setUsed(visited, i);
                if (!map.containsKey(currVisited)) {
                    map.put(currVisited, helper(maxChoosableInteger, desiredTotal - i, currVisited, map));
                }
                if (map.get(currVisited) == false) {
                    flag = true;
                    break;
                }     
            }
        }
        return flag;
    }
   
    private int setUsed(int visited, int num) {
        return visited | (1 << (num - 1));
    }
   
    private boolean isUsed(int visited, int num) {
        return ((visited >> (num - 1)) & 1) == 1;
    }
}

一刷
Version #1 Boolean array

效率很低1.08 %
这个题调了一晚上，一直通不过，一开始以为是toString这个函数用的有什么问题，后来发现不是
bug1
for (int i = used.length - 1; i > 0; i--)  写成for (int i = used.length - 1; i > 0 && !used[i]; i--)
这个bug可以说是非常有价值了，我忘记了中间的;;代表的是终止条件，也就是说一旦不满足就会立刻停止
bug2
对于 5 50这种情况，sum永远不会达到target，所以一开始就要返回FALSE啊！
总体来说boolean array toString效率很低很低，之后再重新写一个用Integer bit manipulation 做hash的

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) return false;
        //used[1] -> 1
        //used[i] -> i
        boolean[] used = new boolean[maxChoosableInteger + 1];
        //Key-Arrays.toString(used), Value-canIWin or not
        //Map<String, Boolean> visited = new HashMap<>();
        return canIWin(used, desiredTotal, new HashMap<String, Boolean>());
    }
    private boolean canIWin(boolean[] used, int desiredTotal, Map<String, Boolean> visited) {
        //System.out.println("String: " + Arrays.toString(used));
        Boolean currVisited = visited.get(Arrays.toString(used));
        if (currVisited != null) return currVisited;
     
        boolean result = false;
        for (int i = used.length - 1; i > 0; i--) {
            if (!used[i]) {
                if (i >= desiredTotal) {
                    //System.out.println(i + "i");
                    result = true;
                    visited.put(Arrays.toString(used), result);
                    return result;
                } else {
                    used[i] = true;
                    if (!canIWin(used, desiredTotal - i, visited)) result = true;
                    //backtracking
                    used[i] = false;
             
                    if (result) {
                        break;
                    }
                }
            }
        }
        visited.put(Arrays.toString(used), result);
        return result;
    }
}