Introduction
DFS is a concept in graph theory; see the DFS (Graph Theory) page for details. In search algorithms, this term often refers to an algorithm that uses recursive functions to conveniently implement brute-force enumeration. It is somewhat similar to the DFS algorithm in graph theory, but is not exactly the same.
Explanation
Consider this example:
Problem
Decompose the positive integer into positive integers, such as , where each number later in the sequence must be greater than or equal to the preceding number, and output all solutions.
For this problem, what should we do if we do not know search? Of course, use three nested loops. The reference code is as follows:
Implementation
C++
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
for (int k = j; k <= n; ++k)
if (i + j + k == n) printf("%d = %d + %d + %d\n", n, i, j, k);
Python
for i in range(1, n + 1):
for j in range(i, n + 1):
for k in range(j, n + 1):
if i + j + k == n:
print("%d = %d + %d + %d" % (n, i, j, k))
Java
for (int i = 1; i < n + 1; i++) {
for (int j = i; j < n + 1; j++) {
for (int k = j; k < n + 1; k++) {
if (i + j + k == n) System.out.printf("%d = %d + %d + %d%n", n, i, j, k);
}
}
}
What if it is decomposed into four integers? Add another loop? What if it is decomposed into no more than integers?
This is when recursive search is needed. This type of search algorithm is characterized by dividing the search target into several “levels”. Each level makes decisions based on the states of the preceding levels until the target state is reached.
Consider the problem above: decompose the positive integer into the sum of no more than positive integers, with each number later in the sequence greater than or equal to the preceding number, and output all solutions.
Suppose one solution decomposes the positive integer into the sum of positive integers . Divide the problem into levels, with level deciding . To make the decision at level , we need to record three state variables: , representing the sum of all positive integers that follow; , representing the positive integer at the preceding level, to ensure that the positive integers are nondecreasing; and , ensuring that we output at most positive integers. To record the solution, we use the arr array, whose -th element represents . Note that arr is actually a stack of length .
The code is as follows:
Implementation
C++
int m, arr[103]; // arr records the solution
void dfs(int n, int i, int a) {
if (n == 0) {
for (int j = 1; j <= i - 1; ++j) printf("%d ", arr[j]);
printf("\n");
}
if (i <= m) {
for (int j = a; j <= n; ++j) {
arr[i] = j;
dfs(n - j, i + 1, j); // Think carefully about the meaning of this line.
}
}
}
// Main function
scanf("%d%d", &n, &m);
dfs(n, 1, 1);
Python
arr = [0] * 103 # arr records the solution
def dfs(n, i, a):
if n == 0:
print(arr[1:i])
if i <= m:
for j in range(a, n + 1):
arr[i] = j
dfs(n - j, i + 1, j) # Think carefully about the meaning of this line.
# Main function
n, m = map(int, input().split())
dfs(n, 1, 1)
Java
static int m;
// arr records the solution
static int[] arr = new int[103];
public static void dfs(int n, int i, int a) {
if (n == 0) {
for (int j = 1; j <= i - 1; j++) System.out.printf("%d ", arr[j]);
System.out.println();
}
if (i <= m) {
for (int j = a; j <= n; ++j) {
arr[i] = j;
dfs(n - j, i + 1, j); // Think carefully about the meaning of this line.
}
}
}
// Main function
final int N = new Scanner(System.in).nextInt();
m = new Scanner(System.in).nextInt();
dfs(N, 1, 1);
Examples
Luogu P1706 Permutation Problem
#include <iomanip>
#include <iostream>
using namespace std;
int n;
bool vis[50]; // Visited markers
int a[50]; // Permutation array, storing the current search result in order
void dfs(int step) {
if (step == n + 1) { // Boundary
for (int i = 1; i <= n; i++) {
cout << setw(5) << a[i]; // Reserve a field width of 5
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) { // Determine whether number i is in the permutation currently being formed
vis[i] = true;
a[step] = i;
dfs(step + 1);
vis[i] = false; // This number is not used at this step; reset it to allow use at the next step
}
}
return;
}
int main() {
cin >> n;
dfs(1);
return 0;
}