DFS

适合于遍历树, 枚举情况等.

属于回溯法的一种.

模板

public void bfs(int i) {
    if (isEnd(i)) {
        // do something ...
    }

    // iterate all options
    for (Object o : getOptions()) {
        if (!isUsed(o)) {
            // update some attributes
            updatePath(i, o);

            // the core backtrack method
            updateState(o);
            dfs(i + 1);
            backtrackState(o);
        }
    }
}

例题

排列数字-acwing

排列数字-acwing

public class acwing_842 {

    int[] path;

    boolean[] state;

    int N;

    public void arrangeNumbers(int n) {
        N = n;
        state = new boolean[N];
        path = new int[N];

        dfs(0);
    }

    void dfs(int i) {
        if (i >= N) {
            System.out.println(Arrays.toString(path));
        }

        for (int j = 0; j < N; j++) {
            if (!state[j]) {
                path[i] = j + 1;

                state[j] = true;
                dfs(i + 1);
                state[j] = false;
            }
        }

    }

    public static void main(String[] args) {
        acwing_842 acwing842 = new acwing_842();
        acwing842.arrangeNumbers(4);
    }

}