797.All Paths From Source to Target

Tags: Medium Backtracking Depth-first Search

Links: https://leetcode.com/problems/all-paths-from-source-to-target/

---

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

• The number of nodes in the graph will be in the range [2, 15].
• You can print different paths in any order, but you should keep the order of nodes inside one path.

---

很典型的回溯程序，有点类似于子集生成。对于每个点存在两种选择，每次将数组tmp加入到res，需要$O(n)$的拷贝时间。所以时间复杂度为$O(n 2^n)$。

class Solution {
    vector<bool> used;

public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = graph.size();
        used.resize(n, false);

        vector<vector<int>> res;
        vector<int> tmp;
        used[0] = true;
        tmp.push_back(0);
        DFS(0, res, tmp, graph);

        return res;
    }

    void DFS(int startPoint, vector<vector<int>> & res, vector<int> & tmp, vector<vector<int>> & graph)
    {
        if (startPoint == (int)graph.size() - 1) {
            res.push_back(tmp); return;
        }

        vector<int> & vec = graph[startPoint];
        for (auto & e : vec) {
            if (!used[e]) {
                used[e] = true;
                tmp.push_back(e);
                DFS(e, res, tmp, graph);
                tmp.pop_back();
                used[e] = false;
            }
        }
    }
};