全排列 + 選擇排列
DeepinScreenshot_select-area_20191003213406.png
數(shù)學(xué)公式：A(n n):需要考慮排列順序
數(shù)學(xué)公式：A(n m): 需要考慮排列順序,
從n個元素中選中m個元素呼畸，進行排列
遞歸法求解
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
// 選中排列
int res=0;
void choosePerm(int pos,int cn,int n,int k,int visit[],int nums[]){
if(cn==k){
for(int i=0;i<k;i++){
cout << nums[i] << " ";
}
cout << endl;
res+=1;
return;
}
if(pos == n) return;
for(int i=0;i<n;i++){
if(visit[i]==0){
visit[i]=cn+1;
// 標(biāo)記結(jié)果
nums[cn]=i;
choosePerm(i,cn+1,n,k, visit, nums);
visit[i]=0;
}
}
}
int main(){
// N: 0-(N-1)
// M: 從 0-(n-1)個數(shù)中選擇M個勇凭，進行全排列(跟順序有關(guān))
// 4!/(4-2)! = 12
// 7!/(7-4)!=7*6*5*4=840
int n=4,k=3;
int visit[n];
int nums[k];
for(int i=0;i<n;i++){
visit[i]=0;
if(i<k){
nums[i]=-1;
}
}
choosePerm(0,0,n,k, visit, nums);
cout << "res-count:" << res << endl;
return 0;
}
復(fù)雜度分析
規(guī)模：N
時間復(fù)雜度：O(M^N), 選中N個元素中的一個元素后煌茴，第二個元素需要從N-1個元素中選取，依然需要遍歷整個序列双妨，第三個元素需要從N-2個元素中選取淮阐，也需要遍歷整個序列。故時間復(fù)雜度: O(M^N)
空間復(fù)雜度：O(N+M), 開了大小為N 的visit數(shù)組用于標(biāo)記-回溯刁品，大小為M的nums數(shù)組用于存儲每趟結(jié)果泣特。
選擇組合
DeepinScreenshot_select-area_20191003213322.png
數(shù)學(xué)公式: C(n m): 從n個元素中選出m個元素進行組合，不考慮順序哑诊。
遞歸法求解
考慮每個元素有兩種可能群扶，1.選中 2.不選中
利用標(biāo)記-回溯方法，記錄選中過程镀裤。
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
void combina(int pos,int cn,int n,int k,int visit[]){
if(cn==k){
for(int i=0;i<n;i++){
if(visit[i]==1){
cout << i << " ";
}
}
cout << endl;
return;
}
if(pos==n) return;
// 1.選擇當(dāng)前pos
if(visit[pos]!=1){
// 標(biāo)記
visit[pos]=1;
combina(pos+1,cn+1,n,k,visit);
// 回溯
visit[pos]=0;
}
// 2.不選擇當(dāng)前pos
combina(pos+1,cn,n,k,visit);
}
int main(){
int n=7;
int k=4;
int visit[n];
combina(0,0,n,k,visit);
return 0;
}
復(fù)雜度分析
規(guī)模：N
時間復(fù)雜度：O(MN),每個元素有兩個選擇竞阐，選與不選，從N中選中第1個元素暑劝，從N-1中選中第2個元素骆莹，從N-2中選中第3個元素，時間復(fù)雜度O(MN).
空間復(fù)雜度：O(N).只需要開大小為N的visit數(shù)組用于標(biāo)記-回溯即可担猛。
參考
csdn: https://blog.csdn.net/hf19931101/article/details/79452799
