문제
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
1
2
3
4
5
6
| 1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
7. "321" Given n and k, return the kth permutation sequence.
|
제한사항
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
입출력 예
1
2
3
4
5
6
7
8
9
| Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
|
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
int count = 0;
bool backTracking(string& cur, int n, int k, vector<bool>& check){
// 현재 문자열 크기가 n이면 리턴이며,
// count가 k가 되도록 순번을 증가시킴
// true로 리턴하여 답을 찾음을 알림
if(cur.size() == n){
++count;
if(count == k)
return true;
return false;
}
// 현재 check가 true인 것만 다음 탐색 시작
// 중간에 재귀로 true를 리턴받으면 답을 찾았다는 것이니
// 이후 계속해서 탐색할 필요가 없음
for(auto i = 1 ; i <= n ; ++i){
if(check[i]){
check[i] = false;
cur.push_back(i + '0');
if(backTracking(cur, n, k, check))
return true;
check[i] = true;
cur.pop_back();
}
}
return false;
}
string getPermutation(int n, int k) {
string answer;
vector<bool> check(n+1, true);
backTracking(answer, n, k, check);
return answer;
}
};
|
