排列组合（选数，填坑问题）

排列组合（选数，填坑问题）

1. 排列：

（1）哈希判重递归
说明：
#适合每个元素互不相同的数列（有相同的会出错）
#每种排列互不相同
#不适合利用全排列枚举求和问题（会有重复）

#include <bits/stdc++.h>
using namespace std;
int x[5]={
    0,1,2,3,4},f[5];
bool hash1[5];
void tiankeng(int pos,int end){
    if(pos==end+1){
    for(int i=1;i<=end;i++){
    cout<<f[i]<<" ";}cout<<endl;return ;}for(int i=1;i<=4;i++){
    if(hash1[x[i]]==false){
    f[pos]=x[i];hash1[x[i]]=true;tiankeng(pos+1,end);hash1[x[i]]=false;}}
}
int main(){
    tiankeng(1,4);
}
结果：
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

（2）利用STL函数简便制作全排列
说明：
#无论元素是否重复都能制造不相同的排列
#不适合全排列枚举求和问题（会有重复）

#include <bits/stdc++.h>
using namespace std;
int x[5]={
    0,1,2,3,4};
int main(){
    do{
    for(int i=1;i<=4;i++){
    cout<<x[i]<<" ";}cout<<endl;}while(next_permutation(x+1,x+1+4));
}
结果：          若将数组中的1改为2  （若此时用法（1）会出现重复的排列，不方便）
1 2 3 4         2 2 3 4
1 2 4 3         2 2 4 3
1 3 2 4			2 3 2 4
1 3 4 2			2 3 4 2
1 4 2 3			2 4 2 3
1 4 3 2			2 4 3 2
2 1 3 4			3 2 2 4
2 1 4 3			3 2 4 2
2 3 1 4			3 4 2 2
2 3 4 1			4 2 2 3
2 4 1 3			4 2 3 2
2 4 3 1			4 3 2 2
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

2.组合

说明：组合即给排列消序（将选出元素内容相同排列视为一种排列）
例如：将1 2 3 4 和 2 1 3 4 视为同一种排列
思路：不降序排列
#数列中有无重复数字都可以
#适用于利用排列枚举求和的问题

#include <bits/stdc++.h>
using namespace std;
int x[6]={
    0,2,2,3,4,5},f[5];
void tiankeng(int start,int pos,int end){
    //end可以控制排列组合的个数如从5个数中挑4个数出来排列组合if(pos==end+1){
    for(int i=1;i<=4;i++){
    cout<<f[i]<<" ";}cout<<endl;return ;}for(int i=start;i<=5;i++){
      f[pos]=x[i];tiankeng(i+1,pos+1,end);   //容易误写成 tiankeng(start+1,pos+1,end)} 
}
int main(){
    tiankeng(1,1,4);
}
结果：
2 2 3 4
2 2 3 5
2 2 4 5
2 3 4 5
2 3 4 5