Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Created October 25, 2016 05:05
Show Gist options
  • Save kartikkukreja/e3572f320af1475cd1e3335aa8f5a180 to your computer and use it in GitHub Desktop.
Save kartikkukreja/e3572f320af1475cd1e3335aa8f5a180 to your computer and use it in GitHub Desktop.
kth permutation recursive solution
int factorial(int n) {
if (n > 12) return INT_MAX;
int f = 1;
for (int i = 2; i <= n; i++)
f *= i;
return f;
}
void getPermutationHelper(vector<int>& num, int k, stringstream& ss) {
if (num.size() == 0) return;
int f = factorial(num.size() - 1);
int incr = k / f;
ss << to_string(num[incr]);
num.erase(num.begin() + incr);
getPermutationHelper(num, k % f, ss);
}
string getPermutation(int n, int k) {
k--; // 0-based indexing
if (k >= factorial(n)) return ""; // error
vector<int> num(n);
for (int i = 0; i < n; ++i)
num[i] = i+1;
stringstream ss;
getPermutationHelper(num, k, ss);
return ss.str();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment