Introduction to depth first search (DFS)

Depth-first search （Deep first serch, abbreviation dfs） yes A search method based on recursion .

You can tell by the name , It's pressing Depth direction The search of . in other words , Choose a way directly to the end , Then choose another way .

Look at the picture

  The sequence of program execution is shown in the figure , Go to the end first , Choose another way .

Example ：

The original title is http://ybt.ssoier.cn:8088/problem_show.php?pid=1317【 Title Description 】

Permutation and combination are common mathematical methods , The combination is from n Out of these elements r Elements ( No order and r≤n), We can simply put n Elements are understood as natural numbers 1,2,…,n, Take any of them r Number .

Now you are required to output all combinations recursively .

for example n＝5,r＝3, All combinations are ：

1 2 3   1 2 4   1 2 5   1 3 4   1 3 5   1 4 5   2 3 4   2 3 5   2 4 5   3 4 5

【 Input 】

Line two natural numbers n、r(1<n<21,1≤r≤n).

【 Output 】

All combinations , Each combination takes up a row, and the elements are arranged from small to large , Each element occupies a position of three characters , All the combinations are also in dictionary order .

【 sample input 】

 5 3

【 sample output 】

123

124

125

134

135

145

234

235

245

345

Examine the subject ： The first number of this problem is from 1 Start , All the way up to 3（ Because it requires dictionary order ）, The remaining numbers can be enumerated in turn

practice ：

1. Defining variables 、dfs function

int n,r,res[30];
void dfs(int num,int pre)// Declare functions  
{
	if(num>r)// If the number of enumerations exceeds r, Output  
	{
		for(int i=1;i<=r;i++) printf("%3d",res[i]);// Each element occupies three characters  
		cout<<endl; 
		return; 
	}
	for(int i=pre+1;i<=n;i++)
	{
		res[num]=i;
		dfs(num+1,i);// recursive  
	}
}

2. Input , The ginseng

int main()
{
	cin>>n>>r;
	dfs(1,0);// first floor  
	return 0;
}

Complete code ：

#include<bits/stdc++.h>
using namespace std;
int n,r,res[30];
void dfs(int num,int pre)// Declare functions  
{
	if(num>r)// If the number of enumerations exceeds r, Output  
	{
		for(int i=1;i<=r;i++) printf("%3d",res[i]);// Each element occupies three characters  
		cout<<endl; 
		return; 
	}
	for(int i=pre+1;i<=n;i++)
	{
		res[num]=i;
		dfs(num+1,i);// recursive  
	}
}
int main()
{
	cin>>n>>r;
	dfs(1,0);// first floor  
	return 0;
}

Novice , Please give me more guidance