# 0294. Flip Game II

<https://leetcode.com/problems/flip-game-ii>

## Description

You are playing a Flip Game with your friend.

You are given a string `currentState` that contains only `'+'` and `'-'`. You and your friend take turns to flip **two consecutive** `"++"` into `"--"`. The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return `true` *if the starting player can **guarantee a win***, and `false` otherwise.

**Example 1:**

```
**Input:** currentState = "++++"
**Output:** true
**Explanation:** The starting player can guarantee a win by flipping the middle "++" to become "+--+".
```

**Example 2:**

```
**Input:** currentState = "+"
**Output:** false
```

**Constraints:**

* `1 <= currentState.length <= 60`
* `currentState[i]` is either `'+'` or `'-'`.

**Follow up:** Derive your algorithm's runtime complexity.

## ac1: backtracking

This key point `if (!nextCanWin) return true;` is the most important breakthrough point。

```java
class Solution {
    public boolean canWin(String s) {
        boolean[] str = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            str[i] = s.charAt(i) == '+' ? true : false;
        }

        return canWinHelper(str);
    }

    private boolean canWinHelper(boolean[] str) {
        // exit
        if (str.length < 2) return false;

        for (int i = 0; i < str.length - 1; i++) {
            if (str[i] && str[i+1]) {
                str[i] = false;
                str[i+1] = false;
                boolean nextCanWin = canWinHelper(str);
                str[i] = true;
                str[i+1] = true;

                if (!nextCanWin) return true;
            }
        }

        return false;
    }
}
```