GabWiki

Appearance

DFS ​

应用 ​

指数型枚举 ​

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

Java
int n;
boolean used = new int[n + 1];

// 尝试选/不选x
void dfs(int x) {
    if (x > n) {
        for (int i = 1; i <= n; ++i) {
            if (used[i]) System.out.print(i + " ");
        }
        System.out.print("\n");
        return;
    }
    dfs(x + 1);
    used[x] = true;
    dfs(x + 1);
    used[x] = false;
}

// usage: dfs(1)
int n;
boolean used = new int[n + 1];

// 尝试选/不选x
void dfs(int x) {
    if (x > n) {
        for (int i = 1; i <= n; ++i) {
            if (used[i]) System.out.print(i + " ");
        }
        System.out.print("\n");
        return;
    }
    dfs(x + 1);
    used[x] = true;
    dfs(x + 1);
    used[x] = false;
}

// usage: dfs(1)
C++
int n;
bool used[N];

// 尝试选/不选x
void dfs(int x) {
    if (x > n) {
        for (int i = 1; i <= n; ++i) {
            if (used[i]) printf("%d ", i);
        }
        return;
    }
    putchar('\n');
    dfs(x + 1);
    used[x] = true;
    dfs(x + 1);
    used[x] = false;
}

// usage: dfs(1)
int n;
bool used[N];

// 尝试选/不选x
void dfs(int x) {
    if (x > n) {
        for (int i = 1; i <= n; ++i) {
            if (used[i]) printf("%d ", i);
        }
        return;
    }
    putchar('\n');
    dfs(x + 1);
    used[x] = true;
    dfs(x + 1);
    used[x] = false;
}

// usage: dfs(1)

组合型枚举 ​

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

Java
int[] chosen = new int[m];

// 尝试把st...n放在chosen[u]
void dfs(int u, int st) {
    if (u + n - st + 1 < m) return; // 剪枝
    if (u == m) {
        for (int x : chosen) System.out.print(x + " ");
        System.out.print("\n");
        return;
    }
    for (int x = st; x <= n; ++x) {
        chosen[u] = x;
        dfs(u + 1, x + 1);
    }
}

// usage: dfs(0, 1)
int[] chosen = new int[m];

// 尝试把st...n放在chosen[u]
void dfs(int u, int st) {
    if (u + n - st + 1 < m) return; // 剪枝
    if (u == m) {
        for (int x : chosen) System.out.print(x + " ");
        System.out.print("\n");
        return;
    }
    for (int x = st; x <= n; ++x) {
        chosen[u] = x;
        dfs(u + 1, x + 1);
    }
}

// usage: dfs(0, 1)
C++
int chosen[M], u;

// 尝试把st...n放在chosen[u]
void dfs(int u, int st) {
    if (u + n - st + 1 < m) return; // 剪枝
    if (u == m) {
        for (int i = 0; i < m; ++i) printf("%d ", chosen[i]);
        putchar('\n');
        return;
    }
    for (int x = st; x <= n; ++x) {
        chosen[u] = x;
        dfs(u + 1, x + 1);
    }
}

// usage: dfs(0, 1)
int chosen[M], u;

// 尝试把st...n放在chosen[u]
void dfs(int u, int st) {
    if (u + n - st + 1 < m) return; // 剪枝
    if (u == m) {
        for (int i = 0; i < m; ++i) printf("%d ", chosen[i]);
        putchar('\n');
        return;
    }
    for (int x = st; x <= n; ++x) {
        chosen[u] = x;
        dfs(u + 1, x + 1);
    }
}

// usage: dfs(0, 1)

排列型枚举 ​

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序方案。

Java
int[] chosen = new int[n];
boolean[] used = new boolean[n + 1];

// 尝试把1...n中没用过的数放在chosen[u]
void dfs(int u) {
    if (u == n) {
        for (int x : chosen) System.out.print(x + " ");
        System.out.print("\n");
        return;
    }
    for (int x = 1; x <= n; ++x) {
        if (!used[x]) {
            chosen[u] = x;
            used[x] = true;
            dfs(u + 1);
            used[x] = false;
        }
    }
}

// usage: dfs(0)
int[] chosen = new int[n];
boolean[] used = new boolean[n + 1];

// 尝试把1...n中没用过的数放在chosen[u]
void dfs(int u) {
    if (u == n) {
        for (int x : chosen) System.out.print(x + " ");
        System.out.print("\n");
        return;
    }
    for (int x = 1; x <= n; ++x) {
        if (!used[x]) {
            chosen[u] = x;
            used[x] = true;
            dfs(u + 1);
            used[x] = false;
        }
    }
}

// usage: dfs(0)
C++
int chosen[N];
bool used[N];

// 尝试把1...n中没用过的数放在chosen[u]
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; ++i) printf("%d ", chosen[i]);
        putchar('\n');
        return;
    }
    for (int x = 1; x <= n; ++x) {
        if (!used[x]) {
            chosen[u] = x;
            used[x] = true;
            dfs(u + 1);
            used[x] = false;
        }
    }
}

// usage: dfs(0)
int chosen[N];
bool used[N];

// 尝试把1...n中没用过的数放在chosen[u]
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; ++i) printf("%d ", chosen[i]);
        putchar('\n');
        return;
    }
    for (int x = 1; x <= n; ++x) {
        if (!used[x]) {
            chosen[u] = x;
            used[x] = true;
            dfs(u + 1);
            used[x] = false;
        }
    }
}

// usage: dfs(0)

剪枝 ​

  • 优化搜索顺序。
    • 大部分情况下，我们应该优先搜索分支较少的节点。
  • 排除等效冗余。
  • 可行性剪枝。
  • 最优性剪枝。
  • 记忆化搜索（DP）。