对数组a[] = {1,2,3,4}进行全排列
可以看成对1{2,3,4},2{1,3,4},3{1,2,4},4{1,2,3}进行全排列
也可以看成对12{3,4},13{2,3},14{2,3},21{3,4},23{1,4},24{1,3},31{2,4},32{1,4},34{1,2},41{3,2},42{3,1},43{1,2}进行全排列
......
即确定前缀，对剩下的元素进行全排列。
双指针，一个确定当前前缀的下标，另一个确定与其交换元素的下标
层层递归，直到当前前缀下标 ＝ 数组的长度len-1(下标从0开始)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 #define mem(a, b) memset(a, b, sizeof a) 5 6 typedef long long ll; 7 int dir8[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; 8 int dir4[4][2] = {1, 0, 0, 1, -1, 0, 0, -1}; 9 const int INF = 0x3f3f3f3f; 10 int mod = 1e9 + 7; 11 const int maxn = 305; 12 void print(int* a) { 13 for(int i = 0; i < 4; i++) { 14 cout << a[i]; 15 if(i < 3) cout << " "; 16 else cout << endl; 17 } 18 } 19 void perm(int* a,int m,int k) { 20 if(m == 3) { 21 print(a); 22 return ; 23 } 24 for(int i = k; i < 4; i++) { 25 swap(a[m],a[i]); 26 perm(a,m+1,k+1); 27 swap(a[m],a[i]); 28 } 29 } 30 int main() 31 { 32 int a[4] = {1,2,3,4}; 33 perm(a,0,0); 34 return 0; 35 }