回溯法(DFS)

应用场景

回溯法的求解目标是找出解空间树中满足约束条件的所有解。

回溯实现全排列

public static void permutation(int[] array, LinkedList<Integer> track) {
        // 到达叶子节点，输出
        if (track.size() == array.length) {
            System.out.println(Arrays.toString(track.toArray()));
        } else {
            for (int j : array) {
                // 包含当前选择，不选择
                if (track.contains(j)) {
                    continue;
                }
                // 加入选择
                track.add(j);
                // 进入下一个决策树
                permutation(array, track);
                // 取消选择
                track.removeLast();
            }
        }
}