CanIWin

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean result = solution.canIWin(10, 40);
        System.out.println(result);
    }

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) {
            return true;
        }
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
            return false;
        }

        // 记录已走过的路径
        Map<String, Boolean> memo = new HashMap<>();
        // 当前数字选用情况
        int[] state = new int[maxChoosableInteger];
        return judge(desiredTotal, memo, state);
    }

    private boolean judge(int desiredTotalNow, Map<String, Boolean> memo, int[] state) {
        String key = Arrays.toString(state);
        System.out.println(key);
        if (memo.containsKey(key)) {
            return memo.get(key);
        } else {
            for (int i = 0; i < state.length; i++) {
                // 未使用过的数字进行处理
                if (state[i] == 0) {
                    // 先置位
                    state[i] = 1;
                    /**
                     * 1.当前目标值小于选中的数值
                     * 2.递归计算剩下的数字组合
                     */
                    if (desiredTotalNow <= i + 1 || !judge(desiredTotalNow - (i + 1), memo, state)) {
                        // 记录下结果
                        memo.put(key, true);
                        // 重要！！ 此处需要复位
                        state[i] = 0;
                        return true;
                    }
                    // 没有成功的路径，此处复位
                    state[i] = 0;
                }
            }
            // 该组合下没有一种可以成功的
            memo.put(key, false);
            return false;
        }
    }
}