/*
Code for generating all permutation of an array using Backtracking
*/
#include<bits/stdc++.h>
using namespace std;
void print(int a[],int n){
for(int i = 0; i < n; i++)cout<<a[i]<<" ";
cout<<endl;
}
int p = 0;
/*assuming all numebers are different in array*/
void generate(int a[],int n,int i){// n = array size
if(i == n){// traveresed entire array
// p++;
print(a,n);
return;
}
for(int j = i; j < n; j++){
swap(a[i],a[j]);//fix element at ith index
generate(a,n,i+1);
swap(a[i],a[j]);//backtrack
}
}
int main(){
int a[]={1,2,3,4,5};
generate(a,5,0);
//cout<<p<<endl;
return 0;
}
LyoKCkNvZGUgZm9yIGdlbmVyYXRpbmcgYWxsIHBlcm11dGF0aW9uIG9mIGFuIGFycmF5IHVzaW5nIEJhY2t0cmFja2luZwoKKi8KCgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBwcmludChpbnQgYVtdLGludCBuKXsKCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspY291dDw8YVtpXTw8IiAiOwoJY291dDw8ZW5kbDsKfQoKaW50ICBwID0gMDsKLyphc3N1bWluZyBhbGwgbnVtZWJlcnMgYXJlIGRpZmZlcmVudCBpbiBhcnJheSovCnZvaWQgZ2VuZXJhdGUoaW50IGFbXSxpbnQgbixpbnQgaSl7Ly8gbiA9IGFycmF5IHNpemUKCWlmKGkgPT0gbil7Ly8gdHJhdmVyZXNlZCBlbnRpcmUgYXJyYXkKCS8vCXArKzsKCQkKCQlwcmludChhLG4pOwoJCXJldHVybjsKCX0KCWZvcihpbnQgaiA9IGk7IGogPCBuOyBqKyspewoJCQoJc3dhcChhW2ldLGFbal0pOy8vZml4IGVsZW1lbnQgYXQgaXRoIGluZGV4CgkKCWdlbmVyYXRlKGEsbixpKzEpOwoJCglzd2FwKGFbaV0sYVtqXSk7Ly9iYWNrdHJhY2sJCgkKCX0KCQp9CgppbnQgbWFpbigpewoJaW50IGFbXT17MSwyLDMsNCw1fTsKCglnZW5lcmF0ZShhLDUsMCk7CgkKICAgIC8vY291dDw8cDw8ZW5kbDsKCXJldHVybiAwOwp9