1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <vector>

class Solution {
    bool DFS(int i, int n, std::vector<int>& visited, std::vector<int>& arr) {
        if (i < 0 || i >= n || visited[i]) {
            return false;
        }
        if (arr[i] == 0) {
            return true;
        }
        visited[i] = true;
        return (DFS(i - arr[i], n, visited, arr) || DFS(i + arr[i], n, visited, arr));
    }
public:
    bool canReach(std::vector<int>& arr, int start) {
        int n = arr.size();
        std::vector<int> visited(n, 0);
        return DFS(start, n, visited, arr);
    }
};