package leetcode;

public class Problem55 {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        for (int i = 0; i < nums.length; i++) {
            if (canJump(nums, i)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean canJump(int[] nums, int idx) {
        int i = idx;
        while (i < nums.length) {
            if (nums[i] == 0) {
                return false;
            }
            int val = (nums.length-1) - i - nums[i];
            if (val == 0) {
                return true;
            }
            i += nums[i];
        }
        return false;
    }
    
    public static void main(String[] args) {
        Problem55 prob = new Problem55();
        System.out.println(prob.canJump(new int[]{2,3,1,1,4}));
        System.out.println(prob.canJump(new int[]{3,2,1,0,4}));
        System.out.println(prob.canJump(new int[]{2,0}));
        System.out.println(prob.canJump(new int[]{0}));
    }
}

@@ -12,16 +12,89 @@
 tcode;%0A%0A
+import java.util.HashSet;%0Aimport java.util.Set;%0Aimport java.util.Stack;%0A%0A
 public c
@@ -163,147 +163,218 @@
     
-if (nums.length == 1) %7B%0A            return true;%0A        %7D%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            if (canJump(nums, i)
+Stack%3CInteger%3E stack = new Stack%3C%3E();%0A        Set%3CInteger%3E set = new HashSet%3C%3E();%0A        stack.add(0);%0A        while (!stack.isEmpty()) %7B%0A            int idx = stack.pop();%0A            if (idx == nums.length-1
 ) %7B%0A
@@ -428,133 +428,110 @@
     
-%7D%0A        return false
+    int val = nums%5Bidx%5D
 ;%0A    
-%7D%0A
     
-%0A
     
-private boolean canJump(int%5B%5D nums, int idx) %7B%0A        int i = idx;%0A        while
+for (int i = idx+1; i %3C= idx+val; i++) %7B%0A                if
  (i 
-%3C
+==
  num
@@ -538,16 +538,18 @@
 s.length
+-1
 ) %7B%0A    
@@ -553,35 +553,8 @@
     
-       if (nums%5Bi%5D == 0) %7B%0A
     
@@ -560,39 +560,41 @@
             
- 
 return 
-false;%0A
+true;%0A    
             
@@ -611,76 +611,82 @@
     
-int val = (nums.length-1) - i - nums%5Bi%5D;%0A            if (val == 0) %7B
+    if (set.contains(i)) %7B%0A                    continue;%0A                %7D
 %0A   
@@ -694,35 +694,34 @@
             
-return true
+set.add(i)
 ;%0A          
@@ -726,35 +726,40 @@
     
-%7D%0A
     
-        i += nums%5Bi%5D;
+stack.push(i);%0A            %7D
 %0A   
@@ -944,24 +944,32 @@
 ,3,1,1,4%7D));
+ // true
 %0A        Sys
@@ -1016,24 +1016,33 @@
 ,2,1,0,4%7D));
+ // false
 %0A        Sys
@@ -1083,24 +1083,32 @@
 nt%5B%5D%7B2,0%7D));
+ // true
 %0A        Sys
@@ -1151,16 +1151,164 @@
 %5B%5D%7B0%7D));
+ // true%0A        System.out.println(prob.canJump(new int%5B%5D%7B0,2,3%7D)); // false%0A        System.out.println(prob.canJump(new int%5B%5D%7B1,0,1,0%7D)); // false
 %0A    %7D%0A%7D

Update problem 55 (stil TLE)