排列搜索

一句话理解

排列搜索：每个位置选一个还没用过的数。

为什么要学

n 全排列、旅行顺序。

讲解

used 数组标记数字是否已用。深度到达 n 记录方案。复杂度 n!。

例子

void dfs(int d) {
    if (d == n) { save(); return; }
    for (int i = 1; i <= n; i++) if (!used[i]) {
        used[i] = 1; a[d] = i;
        dfs(d + 1);
        used[i] = 0;
    }
}

第 d 位尝试所有未用数字。

常见错误

• n=12 无剪枝。
• used 不回溯。