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

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);
    }
}