求n选m（nCm）字典序第k个组合的高效算法咨询

存在远优于O(NK)的高效解法，时间复杂度可以控制在*O(m * min(n, 30))*级别，完全可以满足n、m≤1e4，k≤1e9的计算需求。

核心思路 #

我们可以逐位确定组合的每一位元素，利用组合数快速判断当前位取值：

1. 升序字典序的组合天然满足后一位严格大于前一位，我们从左到右依次确定每一位的数值
2. 假设当前已经确定了前t位的最后一个值为pre，还需要选left = m - t个元素，接下来尝试给第t+1位赋值为cur（cur从pre+1开始递增）
3. 计算如果当前位固定为cur，剩下的left-1个元素从cur+1 ~ n中选的总组合数：c = C(n - cur, left - 1)
4. 如果k <= c：说明目标组合就在当前cur开头的分组中，固定cur为第t+1位，进入下一位的确定流程
5. 如果k > c：说明目标组合不在当前分组，k减去c，cur加1后重复上述判断

示例验证 #

对应题目给出的N=7，M=3，K=6的情况：

1. 初始pre=0，left=3，k=6，cur从1开始试：
   计算C(7-1, 3-1)=C(6,2)=15，6<=15，固定第一位为1，pre=1，left=2
2. 接下来cur从2开始试：
   计算C(7-2, 2-1)=C(5,1)=5，6>5，k=6-5=1，cur=3
   计算C(7-3, 2-1)=C(4,1)=4，1<=4，固定第二位为3，pre=3，left=1
3. 最后cur从4开始试：
   计算C(7-4, 1-1)=C(3,0)=1，1<=1，固定第三位为4
   最终得到结果1 3 4，和示例一致。

关键优化点 #

计算组合数C(a,b)时不需要算出精确的大数值：
因为题目中k最大为1e9，只要计算过程中组合数超过1e9，直接返回1e9 + 1即可，既可以避免整数溢出，也能大幅减少计算量。

参考实现代码 #

def comb_over_limit(a, b, limit):
    if b < 0 or b > a:
        return 0
    if b == 0 or b == a:
        return 1
    b = min(b, a - b) # 利用组合数对称性减少计算
    res = 1
    for i in range(1, b + 1):
        res = res * (a - b + i) // i
        if res > limit:
            return limit + 1
    return res

def get_kth_combination(n, m, k):
    res = []
    pre = 0
    left = m
    for _ in range(m):
        cur = pre + 1
        while True:
            c = comb_over_limit(n - cur, left - 1, k)
            if k <= c:
                break
            k -= c
            cur += 1
        res.append(cur)
        pre = cur
        left -= 1
    return res

# 测试示例
print(get_kth_combination(7, 3, 6)) # 输出 [1,3,4]

复杂度说明 #

• 每确定一位元素，最多试O(n)次，但实际因为组合数增长极快，大部分场景下试算次数远小于n
• 单次组合数计算最多循环O(min(b, 30))次（因为C(1e4, 20)已经远大于1e9）
• 整体复杂度完全可以覆盖题目给出的取值范围，即使k达到1e9也可以在毫秒级完成计算。

内容的提问来源于stack exchange，提问作者unglinh279