0

Question:

Given 3 integers n, m, k (n, m ≤ 10^4; k ≤ 10^9). Find the K'th position of nCm.

Example:

N = 7, M = 3, K = 6.

The first 6 7C3 permutations are:

  • 1 2 3
  • 1 2 4
  • 1 2 5
  • 1 2 6
  • 1 2 7
  • 1 3 4

So the answer would be 1 3 4

P/S: I only know how to solve this problem using brute force, which takes O(N*K). Is there any better solution for this problem?

unglinh279
  • 675
  • 4
  • 24
  • 1
    Does this answer your question? [How to get the kth term in N Combination R](https://stackoverflow.com/a/51848026/16757174) – kcsquared Sep 11 '21 at 05:46
  • 1
    @kcsquared The best answer to the question you linked explains how to find the kth permutation, not the kth combination. Then it ends with the encouraging sentence *"These concepts extends to other types of combinatorial problems, such as finding the nth combination, or permutation with repetition, etc."*. – Stef Sep 11 '21 at 09:41
  • 1
    Search for "unrank" combination. – גלעד ברקן Sep 11 '21 at 13:42

0 Answers0