Submission #74976271

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/**
めっちゃbacktrackぽい
Sの全てのパターンの並び方のK番目
注意なのが、重複はカウントしないこと

*/
static bool backtrack(string &current, string &remaining, int &K) {
  if (remaining.empty()) {
    K--;
    if (K == 0) {
      cout << current << endl;
      return true;
    }
    return false;
  }

  int n = remaining.size();
  for (int i = 0; i < n; i++) {
    if (i > 0 && remaining[i] == remaining[i - 1]) continue;
    // 1文字選ぶ
    current.push_back(remaining[i]);

    // 残りを作る
    string next = remaining.substr(0, i) + remaining.substr(i + 1);
    if (backtrack(current, next, K)) return true;

    current.pop_back();
  }
  return false;
}

int main() {
  string S;
  int K;
  cin >> S >> K;

  // 辞書順にするためにまずソート
  sort(S.begin(), S.end());

  string current;
  backtrack(current, S, K);
  return 0;
}

Submission Info

Judge Result