> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/hard/55.-jump-game.md).

# 55. Jump Game

***

### Intuition

* We can use the back-tracking approach , with memorisation to avoid duplicate effort

### Approach

* When at $i$ try taking all possible jumps and return if any one works.

### Complexity

* | **Time complexity** : $\text{O}()$ |
  | ---------------------------------- |
* | **Space complexity** : $\text{O}()$ |
  | ----------------------------------- |

### Code

```java
class Solution {
    Set < Integer > failing = new HashSet < > ();

    public boolean jumping(int[] nums, int i) {
        if (i >= nums.length - 1)
            return true;

        if (nums[i] == 0)
            return false;

		for (int j = Math.min(nums[i],nums.length - i) ; j > 0; --j) {
            if (failing.contains(i + j))
                continue;

            if (jumping(nums, i + j))
                return true;

            failing.add(i + j);
        }

        return false;
    }

    public boolean canJump(int[] nums) {
        return jumping(nums, 0);
    }
}
```