【NOIP算法：回溯】基础问题3：组合+全排列问题

问题描述

求从m个数中取r个数，（m、r都是大于0的正整数，且r<m<=15）。

输入格式：

       第一行 m  r
       第二行 输入m个正整数

输出格式：

       所有可能的组合的全排列。
【样例输入】：

          3   2
          1   2   3
【样例输出】：
          3    2
          2    3
          3    1
          1    3
          2    1
          1    2

参考代码

#include<iostream>
#include<cstring>
using namespace std;#define MAX 15 
int A[MAX],B[MAX];
int M,R;
void print(int A[],int n)
{for(int i=0;i<n;i++){cout<<A[i]<<" ";}cout<<endl;
} 
void swap(int A[],int p,int i)
{int temp = A[p];A[p] = A[i];A[i] = temp;
}
void perm(int A[],int p,int q)
{if(p==q){print(A,q+1);}for(int i=p;i<=q;i++){swap(A,p,i);	//第一步：依次完成当前数组首元素 （p）和后续元素位置的交换 perm(A,p+1,q);	//第二步：将当下数组首元素之后的所有元素做全排列 swap(A,p,i);	//第三步：在下一次全排列之前记得将元素交换回来 }
}void comb(int m,int r)
{int i;if(r==0){perm(B,0,R-1);	//得到一个组合，做全排列 return; }else{for(int i=m-1;i>=0;i--){B[r-1]=A[i];	//当前数组的最后一个元素作为定元素 comb(i,r-1);	//在剩余m-1个元素种，选择r-1个元素 }}
}
int main()
{cin>>M>>R;for(int i=0;i<M;i++){cin>>A[i];}comb(M,R); return 0;
}

具体分析过程，稍后再补充~

—<完>—