> For the complete documentation index, see [llms.txt](https://programming.arora-aditya.com/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://programming.arora-aditya.com/leetcode/backtracking/294.-flip-game-ii.md).

# 294. Flip Game II

### Approach 1: Brute force all ways using Recursion

```python
class Solution:
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        for i in range(len(s)-1):
            if s[i]+s[i+1] == '++' and not self.canWin(s[:i]+'--'+s[i+2:]):
                return True
        return False
```

This solution looks at all the possible ways any two ++'s can be replaced and continues to check using recursion if there was a way that the player cannot win. If it finds a way, then it stops and returns `True`, else it continues looking. If it does not find any such way to guarantee a win, it returns `False`

The solution is very slow since it looks at all possible ways if False, and comes in at a lowly 2.2% percentile

> **Time Complexity:** *O(1), fixed object size*
>
> **Space Complexity:** *O(1), fixed object size*