回溯时如何存储递归结果？递归排列生成代码无法留存结果求助

我明白你的问题了——这段回溯代码能正确打印排列，但没法把结果持久存储下来，本质是因为你操作的是同一个可变列表对象，回溯时的修改会覆盖之前的内容，对吧？

问题根源 #

原代码里的result是一个可变的列表，所有递归调用共享同一个列表的引用。当递归终止时打印，此时列表内容是正确的排列，但如果直接把result添加到收集列表里，你存的只是这个列表的"指针"——后面回溯修改元素时，之前存的所有条目都会跟着变化，最后得到的全是最后一次修改的结果。

修改方案：存储结果的副本 #

解决的核心是在递归终止时，存储result的副本而非原引用。下面给你两种可行的修改方式：

方式1：传入外部列表收集结果（更直观）

def permute_util(str_list, count, result, level, output):
    if level == len(result):
        # 把当前排列转成字符串（不可变）或者创建列表副本存入
        current_perm = ''.join(result)
        print(current_perm)
        output.append(current_perm)
        return
    for i in range(len(str_list)):
        if count[i] == 0:
            continue
        result[level] = str_list[i]
        count[i] -= 1
        permute_util(str_list, count, result, level + 1, output)
        count[i] += 1

# 调用示例（修正了你之前count数组的笔误，假设每个字符出现1次）
input_str = "ABC"
count_arr = [1] * len(input_str)
result_temp = [None] * len(input_str)
output_list = []
permute_util(list(input_str), count_arr, result_temp, 0, output_list)

print("\n存储的所有排列：")
print(output_list)

方式2：让函数返回收集到的结果（更函数式）

def permute_util(str_list, count, result, level):
    output = []
    if level == len(result):
        current_perm = ''.join(result)
        print(current_perm)
        output.append(current_perm)
        return output
    for i in range(len(str_list)):
        if count[i] == 0:
            continue
        result[level] = str_list[i]
        count[i] -= 1
        # 递归收集子问题的排列结果
        sub_results = permute_util(str_list, count, result, level + 1)
        output.extend(sub_results)
        count[i] += 1
    return output

# 调用示例
input_str = "ABC"
count_arr = [1] * len(input_str)
result_temp = [None] * len(input_str)
output_list = permute_util(list(input_str), count_arr, result_temp, 0)

print("\n存储的所有排列：")
print(output_list)

关键说明 #

• 不管用哪种方式，核心都是避免直接存储原result列表：用''.join(result)转成不可变的字符串，或者用result.copy()创建新列表，这样后续回溯修改不会影响已经存储的内容。
• 你之前count数组里的[2,...应该是笔误，如果是处理重复字符的排列（比如"AAB"），只需要把count_arr改成对应字符的出现次数（比如[2,1]）即可，原有的去重逻辑是有效的。

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