Python实现有序字符拆分：生成所有保持原序的拆分子集

核心逻辑 #

输入字符串有n个字符时，相邻字符间存在n-1个可选拆分点——每个点要么拆分（将前后字符分为两段），要么不拆分（合并为同一段）。所有拆分组合的总数正好是2^(n-1)，和你计算的一致。回溯法的核心就是遍历所有拆分点的选择组合，逐步构建出所有合法拆分结果。

代码实现（Python） #

def generate_splits(s):
    splits = []
    
    def backtrack(start_idx, current_segments):
        # 处理完所有字符，记录当前拆分结果
        if start_idx == len(s):
            splits.append(tuple(current_segments))
            return
        
        # 从当前起始位置开始，尝试所有可能的结束位置（不拆分，继续合并字符）
        for end_idx in range(start_idx + 1, len(s) + 1):
            # 将当前子串作为一段加入临时结果
            current_segments.append(s[start_idx:end_idx])
            # 递归处理下一段的起始位置
            backtrack(end_idx, current_segments)
            # 回溯：移除当前段，尝试其他拆分方式
            current_segments.pop()
    
    backtrack(0, [])
    return splits

# 可选：按示例格式输出结果
def print_formatted_splits(s):
    splits = generate_splits(s)
    formatted = [f"({','.join(seg)})" for seg in splits]
    print('、'.join(formatted))

代码说明 #

1. 回溯函数参数：start_idx标记当前要处理的字符起始位置，current_segments记录当前已构建的拆分段列表。
2. 终止条件：当start_idx等于字符串长度时，说明所有字符已处理完毕，将当前拆分结果转为元组存入最终列表。
3. 遍历选择：从start_idx+1到字符串末尾，逐个尝试将start_idx到end_idx的子串作为一段，递归处理后续字符；递归返回后弹出当前段，继续尝试更长的子串（即不拆分后续字符的情况）。
4. 重复字符兼容：逻辑仅依赖字符位置截取子串，和字符内容无关，天然支持含重复字符的输入。

测试示例 #

• 调用print_formatted_splits("ab")，输出：(a,b)、(ab)
• 调用print_formatted_splits("abc")，输出：(a,b,c)、(a,bc)、(ab,c)、(abc)
• 调用print_formatted_splits("abcd")，输出结果和你给出的示例完全一致。

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