Skip to content

DFS (Search)

Introduction

DFS is a concept in graph theory; for details, refer to the DFS (Graph Theory) page. In the context of search algorithms, this term often refers to algorithms that conveniently implement brute-force enumeration using recursive functions. It shares some similarities with the DFS algorithm in graph theory but is not entirely the same.

Explanation

Consider this example:

Example Problem

Decompose the positive integer \(n\) into three positive integers, such as \(6=1+2+3\), where each subsequent number must be greater than or equal to the previous one. Output all possible decompositions.

For this problem, if you are not familiar with search algorithms, what would you do? Naturally, you would use three nested loops, as shown in the reference code below:

Implementation 
1
2
3
4
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);

1
2
3
4
5
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))

1
2
3
4
5
6
7
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);
        }
    }
}

But what if we need to decompose it into four integers? Add another loop? And what about decomposing it into at most \(m\) integers?

This is where recursive search comes into play. The characteristic of such search algorithms is that they divide the search target into several "layers," where each layer makes decisions based on the states of previous layers until the target state is reached.

Consider the problem above: decompose the positive integer \(n\) into at most \(m\) positive integers, where each subsequent number must be greater than or equal to the previous one, and output all possible decompositions.

Suppose a decomposition splits the positive integer \(n\) into \(k\) positive integers \(a_1, a_2, \ldots, a_k\). The problem is divided into layers, where the \(i\)-th layer determines \(a_i\). To make the decision for the \(i\)-th layer, we need to record three state variables: \(n-\sum_{j=1}^i{a_j}\), representing the sum of all remaining positive integers; \(a_{i-1}\), representing the positive integer from the previous layer to ensure the numbers are non-decreasing; and \(i\), ensuring we output at most \(m\) positive integers. To record the decomposition, we use an array arr, where the \(i\)-th element represents \(a_i\). Note that arr is essentially a stack of length \(i\).

The code is as follows:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int m, arr[103];  // arr is used to record the decomposition

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);  // Please think carefully about the meaning of this line.
    }
  }
}

// Main function
scanf("%d%d", &n, &m);
dfs(n, 1, 1);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
arr = [0] * 103  # arr is used to record the decomposition


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)  # Please think carefully about the meaning of this line.


# Main function
n, m = map(int, input().split())
dfs(n, 1, 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int m;

// arr is used to record the decomposition
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); // Please 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);

Example Problems

Luogu P1706 Full Permutation Problem 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iomanip>
#include <iostream>
using namespace std;
int n;
bool vis[50];  // Visited marker array
int a[50];     // Permutation array, stores current search results in order

void dfs(int step) {
  if (step == n + 1) {  // Boundary condition
    for (int i = 1; i <= n; i++) {
      cout << setw(5) << a[i];  // Reserve 5-character field width
    }
    cout << endl;
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {  // Check if number i is already in the current permutation
      vis[i] = true;
      a[step] = i;
      dfs(step + 1);
      vis[i] = false;  // This step does not use this number, reset to 0 to allow use in next step
    }
  }
  return;
}

int main() {
  cin >> n;
  dfs(1);
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用