I just solved the following Leetcode problem: All Paths From Source to Target

Here is my solution:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> curr = { 0 };
        backtrack(graph, curr, 0);
        return answer;
    }
private:
    vector<vector<int>> answer;
    void backtrack(vector<vector<int>>& graph, vector<int>& curr, int node) {
        if (node == graph.size() - 1) {
            answer.push_back(curr);
            return;
        }

        for (int neighbor : graph[node]) {
            curr.push_back(neighbor);
            backtrack(graph, curr, neighbor);
            curr.pop_back();
        }
    }
};

I was told that the time complexity of the algorithm is $O(n \cdot 2 ^ n)$, because there are at most $2^n$ different paths in the graph, and for each path, we do $O(n)$ work to copy the path to the answer array.

However, this only represents the leaf nodes part of the recursion tree, how about the work done in leaf nodes of the recursion tree? I understand that the work done at every non-leaf node is $O(1)$ but how do I know how many there are?

I just solved the following Leetcode problem: All Paths From Source to Target

Here is my solution:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> curr = { 0 };
        backtrack(graph, curr, 0);
        return answer;
    }
private:
    vector<vector<int>> answer;
    void backtrack(vector<vector<int>>& graph, vector<int>& curr, int node) {
        if (node == graph.size() - 1) {
            answer.push_back(curr);
            return;
        }

        for (int neighbor : graph[node]) {
            curr.push_back(neighbor);
            backtrack(graph, curr, neighbor);
            curr.pop_back();
        }
    }
};

I was told that the time complexity of the algorithm is $O(n \cdot 2 ^ n)$, because there are at most $2^n$ different paths in the graph, and for each path, we do $O(n)$ work to copy the path to the answer array.

However, this only represents the leaf nodes part of the recursion tree, how about the work done in non-leaf nodes of the recursion tree? I understand that the work done at every non-leaf node is $O(1)$ but how do I know how many there are?

I just solved the following Leetcode problem: https://leetcode.com/problems/all-paths-from-source-to-target/description/

Here is my solution:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> curr = { 0 };
        backtrack(graph, curr, 0);
        return answer;
    }
private:
    vector<vector<int>> answer;
    void backtrack(vector<vector<int>>& graph, vector<int>& curr, int node) {
        if (node == graph.size() - 1) {
            answer.push_back(curr);
            return;
        }

        for (int neighbor : graph[node]) {
            curr.push_back(neighbor);
            backtrack(graph, curr, neighbor);
            curr.pop_back();
        }
    }
};

I was told that the time complexity of the algorithm is O(n x 2 ^ n), because there are at most 2^n different paths in the graph, and for each path, we do O(n) work to copy the path to the answer array. However, this only represents the leaf nodes part of the recursion tree, how about the work done in leaf nodes of the recursion tree? I understand that the work done at every non-leaf node is O(1) but how do I know how many there are?

Thank you in advance.

I just solved the following Leetcode problem: All Paths From Source to Target

Here is my solution:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> curr = { 0 };
        backtrack(graph, curr, 0);
        return answer;
    }
private:
    vector<vector<int>> answer;
    void backtrack(vector<vector<int>>& graph, vector<int>& curr, int node) {
        if (node == graph.size() - 1) {
            answer.push_back(curr);
            return;
        }

        for (int neighbor : graph[node]) {
            curr.push_back(neighbor);
            backtrack(graph, curr, neighbor);
            curr.pop_back();
        }
    }
};

I was told that the time complexity of the algorithm is $O(n \cdot 2 ^ n)$, because there are at most $2^n$ different paths in the graph, and for each path, we do $O(n)$ work to copy the path to the answer array. 

However, this only represents the leaf nodes part of the recursion tree, how about the work done in leaf nodes of the recursion tree? I understand that the work done at every non-leaf node is $O(1)$ but how do I know how many there are?