P2404 问题描述
自然数的拆分问题 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
输入输出样例
Sample Input
7
Sample Output
1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4
Wrong Answer
#include <bits/stdc++.h>
using namespace std
;
int n
;
vector
<int> track
;
void dfs(int sum
)
{
if(sum
==n
){
cout
<<track
[0];
for(int i
=1;i
<track
.size();i
++) cout
<<"+"<<track
[i
];
cout
<<endl
; return ;
}
for(int i
=1;i
+sum
<=n
;i
++){
track
.push_back(i
);
dfs(sum
+i
);
track
.pop_back();
}
}
int main()
{
cin
>>n
;
dfs(0);
return 0;
}
这个代码的错误之处就在于深搜时每个分支都从1开始，实际上这样写的话会造成排列重复，比如1+1+1+1+1+2 和1+1+1+1+2+1 都会输出。 措施：观察样例我们发现，后面输出的数总是大于等于前面输出的数，因此可以引入前缀，每次都从前缀的值开始循环。 同时，注意循环结束的条件。
改进
#include <bits/stdc++.h>
using namespace std
;
int n
;
vector
<int> track
;
void dfs(int pre
,int sum
)
{
if(sum
==n
){
cout
<<track
[0];
for(int i
=1;i
<track
.size();i
++) cout
<<"+"<<track
[i
];
cout
<<endl
; return ;
}
for(int i
=pre
;i
+sum
<=n
&&i
!=n
;i
++){
track
.push_back(i
);
dfs(i
,sum
+i
);
track
.pop_back();
}
}
int main()
{
cin
>>n
;
dfs(1,0);
return 0;
}
P1157 问题描述
组合的输出 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素, 请你输出所有组合。我们可以简单地将n个元素理解为自然数1,2,…,n，从中任取r个数。 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
输入输出样例
Sample Input
5 3
Sample Output
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
思路1
using namespace std
;
int n
,r
;
vector
<int> track
;
void dfs(int dep
)
{
if(dep
==n
+1){
if(track
.size()==r
){
for(int i
=0;i
<r
;i
++) printf("%3d",track
[i
]);
cout
<<endl
;
}
return;
}
else{
track
.push_back(dep
);
dfs(dep
+1);
track
.pop_back();
dfs(dep
+1);
}
}
int main()
{
cin
>>n
>>r
;
dfs(1);
return 0;
}
这是在求子集的基础上，只在筛选条件上选择子集个数为r的子集输出，需要耗费较高的时间。
思路2
#include <bits/stdc++.h>
using namespace std
;
int n
,r
;
vector
<int> track
;
void dfs(int pre
)
{
if(track
.size()==r
){
for(int i
=0;i
<r
;i
++) printf("%3d",track
[i
]);
cout
<<endl
; return ;
}
for(int i
=pre
;i
<=n
;i
++){
track
.push_back(i
);
dfs(i
+1);
track
.pop_back();
}
}
int main()
{
cin
>>n
>>r
;
dfs(1);
return 0;
}
P1157拓展
根据思路2，不仅可以写出组合的输出C(m,n)，还可以写出排列的输出A(m,n) 需要一个vis数组判断该数是否已加入track数组
#include <bits/stdc++.h>
using namespace std
;
int n
,r
;
vector
<int> track
;
int vis
[25];
void dfs(int dep
)
{
if(dep
>r
){
for(int i
=0;i
<r
;i
++) printf("%3d",track
[i
]);
cout
<<endl
; return ;
}
for(int i
=1;i
<=n
;i
++){
if(!vis
[i
]){
track
.push_back(i
);
vis
[i
]=1;
dfs(dep
+1);
track
.pop_back();
vis
[i
]=0;
}
}
}
int main()
{
cin
>>n
>>r
;
dfs(1);
return 0;
}
