当前位置：首页 > article >正文

dfs枚举问题

article 2025/2/2 11:30:01

碎碎念：要开始刷算法题备战蓝桥杯了，一切的开头一定是dfs

定义

枚举问题就是咱数学上学到的，从n个数里面选m个数，有三种题型(来自Acwing)

从 1∼n 这 n个整数中随机选取任意多个，输出所有可能的选择方案。
把 1∼n这 n个整数排成一行后随机打乱顺序，输出所有可能的次序
从 1∼n这 n个整数中随机选出 m个，输出所有可能的选择方案。

模版

我觉得这三个都可以由同一套板子来做

int path[N];
bool visited[N]
void dfs(int pos, int start, int n, int m)
//pos指的当前枚举位置
//start指开始的值(为了防止有的题目要求递增输入)
//n指的总元素
//m指的从n个里面挑m个进行枚举

这是通用的dfs定义,path存储每个位置放的元素的值，visited表示该元素是否访问过

逐个分析

在这里插入图片描述

对于这个，可以看到输出样例中他的一共有多少个数不固定，我们可以理解为从n个位置里面挑m个位置，本题没有要求以什么形式输出，为了规整，我默认写的是先1个位置，再两个位置，再三个位置，而且以升序排列
其dfs定义为

void dfs(int pos, int start, int m, int n)  //这个n又表示有多少个数
{
	if(pos > m)
	{
	   for(int i = 1; i <= m; i++)  //这个i循环的是位置，所以一直到m
	   	cout << path[i]<<" ";
	}
	else
	{
		for(int i = start; i <= n; i++)  //这个i循环的是元素的值，所以一直到n
		{
			if(!visited[i])
			{
				visited[i] = false;
				path[pos] = i;
				dfs(pos+1, i+1, m , n)  //这里是i+1,而不是start+1
	//后一个位置的值一定比当前位置值大，已知当前位置的值为i，则下一位置最低也得是i+1
			}
		}
	}
}


int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		dfs(1, 1, i, n)   //这个就是从n个位置选m个
}

第二个
在这里插入图片描述
这个就相当于从n个里面选n个，也不要求顺序了，则start可以当做没有

void dfs(int pos, int n)//这个n既代表位置，又代表元素的值
{
    if(pos > n)
    {
        for(int i = 1; i <= n; i++)
        {
            cout << path[i]<<" ";
            
        }
        cout<<endl;
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                path[pos] = i;
                dfs(pos+1, n);  //是去下一个位置
                visited[i] = false;
            }
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
}

第三个
在这里插入图片描述
从n个元素里面选m个元素，位置最大也是m个，相当于第一种情况的m变式

void dfs(int pos, int start, int n, int m) //开始的值，当前位置
{
    if(pos > m)  
    {
        for(int i = 1; i <= m; i++)
            cout <<path[i]<<" ";
        cout << endl;
    }
    else
    {
        for(int i = start; i <= n; i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                path[pos] = i;
                dfs( pos+1, i+1, n,m);
                visited[i] = false;
            }
        }
    }
}


int main()
{
    cin >> n >> m;
    dfs(1, 1, n, m);
    return 0;
}