实现递归函数k_size_subsets(n,k)生成指定大小的升序子集

问题描述 #

需要实现递归函数 def k_size_subsets(n, k)：

• 接收两个整数n和k，返回集合{1,2,...,n}中所有大小为k的子集组成的列表。
• 每个子集必须以升序字符串表示（如{2,3,4}需写为"234"，不能是"342"）。
• 约束条件：n≥k≥0且1≤n≤9，禁止使用循环、列表和字符串内置方法（len除外）、集合，需采用递归实现，可编写辅助函数但不允许函数嵌套。

示例 #

• k_size_subsets(5,3) 返回['123', '124', '125', '134', '135', '145', '234', '235', '245', '345']
• k_size_subsets(5,0) 返回[]

用户当前尝试的代码 #

def helper_k_size_subsets(n, k, lst, index, delete, swap_digit_sum, final_sum):
    s = lst[index]
    if len(s) != k:
        next_number = chr(ord(s[len(s)-1])+1)
        s = s + next_number
        lst[index] = s
        string_sum = get_sum_of_string(0, s[len(s)-(n-k):], 0)
        string_final_sum = get_sum_of_string(0, s, 0)
        if string_final_sum == final_sum:
            return lst
        if string_sum == swap_digit_sum:
            if delete < k - 1:
                delete += 1
            if int(s[-delete]) + 1 == int(s[-delete + 1]):
                next_s = s[:len(s) - delete - 1] + chr(ord(s[len(s) - delete - 1]) + 1)
                lst += [next_s]
                index += 1
                return helper_k_size_subsets(n, k, lst, index, delete, swap_digit_sum, final_sum)
            next_s = s[:len(s)-delete] + chr(ord(s[len(s)-delete])+1)
            lst += [next_s]
            index += 1
            return helper_k_size_subsets(n, k, lst, index, delete, swap_digit_sum, final_sum)
        else:
            return helper_k_size_subsets(n, k, lst, index, delete, swap_digit_sum, final_sum)
    else:
        next_number = chr(ord(s[len(s)-1]) + 1)
        s = s[:-1] + next_number
        lst[index] = s
        string_final_sum = get_sum_of_string(0, s, 0)
        if string_final_sum == final_sum:
            return lst
        return helper_k_size_subsets(n, k, lst, index, delete, swap_digit_sum, final_sum)

def get_sum_of_string(index, str, sum):
    if index == len(str):
        return sum
    sum += int(str[index])
    return get_sum_of_string(index+1, str, sum)

def get_sum_by_range(begin, end):
    if begin > end:
        return 0
    return begin + get_sum_by_range(begin + 1, end)

def k_size_subsets(n, k):
    if k == 0:
        return []
    swap_digit_sum = get_sum_by_range(n - k + 1, n)
    final_sum = get_sum_by_range(1, k)
    lst = ['1']
    index = 0
    return helper_k_size_subsets(n, k, lst, index, 2, swap_digit_sum, final_sum)

代码验证与正确实现方案 #

原代码问题分析 #

原代码逻辑复杂且存在多处错误，无法正确生成所有符合要求的子集：

1. 依赖字符串切片操作（如s[:len(s)-delete]），违反题目禁止使用字符串内置方法（len除外）的约束。
2. 基于数字和判断的逻辑无法覆盖所有子集场景，测试用例无法得到完整结果。
3. 递归终止条件设计不合理，仅通过数字和判断终止，容易遗漏或提前终止递归流程。

正确递归实现方案 #

基于选与不选的递归思路：对于数字i（从1到n），有两种选择：

• 选i：将其加入当前子集，从i+1开始继续选剩下的k-1个元素。
• 不选i：直接从i+1开始选k个元素。

通过辅助函数处理当前起始数字、剩余需选元素数量、已构建的子集字符串，最终收集所有符合条件的结果。

def k_size_subsets(n, k):
    if k == 0:
        return []
    return helper(n, 1, k, "")

def helper(n, start, remaining, current):
    # 递归终止：已选够k个元素，返回当前子集字符串
    if remaining == 0:
        return [current]
    # 没有更多元素可选，返回空列表
    if start > n:
        return []
    # 选当前start数字，剩余需选数量减1，起始数字加1
    choose = helper(n, start + 1, remaining - 1, current + str(start))
    # 不选当前start数字，剩余数量不变，起始数字加1
    not_choose = helper(n, start + 1, remaining, current)
    # 递归合并两个结果列表
    return combine_lists(choose, not_choose)

def combine_lists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    # 取list1第一个元素，递归合并剩余部分与list2
    return [list1[0]] + combine_lists(list1[1:], list2)

代码说明 #

1. 边界处理：k=0时直接返回空列表，符合题目要求。
2. 辅助函数逻辑：
   • remaining代表还需选的元素数量，为0时当前current就是一个有效子集，返回包含它的列表。
   • 分“选”和“不选”两种递归分支，保证所有可能的子集都被覆盖。
3. 列表合并：通过combine_lists递归合并结果，避免使用循环，符合约束条件。
4. 升序保证：每次拼接的start是递增的，因此生成的子集字符串天然是升序的。

测试验证 #

• 调用k_size_subsets(5,3)，返回结果与示例完全一致。
• 调用k_size_subsets(5,0)，返回[]，符合要求。

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