回溯法--排列组合类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void dfs(int k)
{
	if(到达终点或者目的地）
	{
		输出问题解或者解得方案数+1；
		}
	for(int i = 0;i<="可扩展状态总数";i++)
	{
		按照规则，产生新的状态；
		if(判断新状态是否合法）
		{
			 保存合法结果;
			 dfs(k+1);
			 恢复现场，回溯；//可以没有，根据情况来定
		}
	}
}
int main()
{
	.....
	dfs(k);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n;
void dfs (int k)
{
	if(k==n+1)
	{
		输出数组a[];
		}
	for(int i=1;i<=n;i++)
	{
		if(i是可用的）
		{
			a[k]=i;//保存当前的结果
			 dfs(k+1);//继续搜索第k+1个数
			  恢复现场，回溯；
		}
	}
}
int main()
{
	cin >> n;
	dfs(1);
 return 0;
 }

1
2
3
4
5
6
7
8
9
bool judge(int x,int y)
{
	bool flag = true;
	for(int i = 1;flag && i < x;i++)
	{
		if(a[i]==y) flag = false;
	}
	return flag;

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
32
33
34
#include<iostream>
using namespace std;
int a[102];
int vist[102]={0};
int n;//两个函数公用n,要使用全局变量。
void dfs(int k)
{
  if(k==n+1)//已经放到n+1位置，说明已经完成任务
  {
      for(int i = 1;i <= n;i++) cout<<a[i]<<" ";
      cout<<endl;
  }
  for(int i = 1;i <=n;i ++)
  {
      if(vist[i]==0)//i可以使用
      {
          a[k]=i;
          vist[i]=1;//标记i已经被使用过了
          dfs(k+1);//继续搜索第k+1个数
          vist[i]=0;//回溯，把已经使用的i退回去
      }


  }

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

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
32
33
34
35
36
37
38
39
40
#include<iostream>
 using namespace std;
 const int N = 10;
 int path[N];
 int vis[N]={ 0 };
 int n;
 int a[N];
 void dfs(int k)
 {
     if(k==n+1)
     {
         for(int i= 1;i <=n;i++)
         {
              cout<< path[i]<<" ";
         }
         cout<<endl;
         return ;
     }
     for(int i = 1;i <=n;i++)
     {
         if(!vis[i])
         {
             path[k]=a[i];//注意此处的变化
             vis[i]=1;
             dfs(k+1);
             vis[i]=0;
         }
     }

 }
 int main()
 {
     cin >> n;
     for(int i = 1;i <=n ;i++) cin >> a[i];//注意该代码是什么意思
     dfs(1);
     return 0;

 }

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
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 30
using namespace std;
int n,r;
int a[N];
int vis[N];
void dfs(int step)
{
    int i;

    if(step==r+1)
    {
        for(i=1;i<=r;i++)
            cout<<"  "<<a[i];
        cout<<endl;
        return;
    }

    for(i=a[step-1];i<=n;i++)//从当前已经选择的位置向后选
    {
        if(vis[i]==0)
        {
            a[step]=i;
            vis[i]=1;

            dfs(step+1);

            vis[i]=0;
        }
    }
}
int main()
{
    cin>>n>>r;
    a[0]=1;
    dfs(1);
    return 0;
}

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
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int a[105];
bool used[105];
int ans[105];
int n,t;
int sum = 0;
int x = 0;
void dfs(int index)
{
	if(sum==t)
	{
		for(int i = 1;i<=x;i++) cout<<ans[i]<<" ";
		cout<<endl;
		return ;
	}
	for(int i = index;i<=n;i++)
	{
	//used[i-1]==ture,说明 同一树枝使用过a[i-1]元素；used[i-1]==false,说明同一树层使用过a[i-1]元素 
		if(i>0&&a[i]==a[i-1]&&used[i-1]==false) continue;
		sum+=a[i];
		ans[++x]=a[i];
		used[i]=true;
		dfs(i+1);
		//开始回溯
		sum-=a[i];
		used[i]=false;
		x--;	 
	}
}
int main()
{
	cin>>n>>t;
	for(int i = 1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1); 
	dfs(1);
	return 0;
}