Go 语言实现字符串全排列算法（含源码）

背景

在算法设计与计算机科学领域，排列（Permutation）是一个非常基础且重要的概念。

所谓排列，是指从给定元素集合中，按照一定顺序选取所有元素形成的不同序列。

例如字符串 "abc" 的所有排列为：

• abc
• acb
• bac
• bca
• cab
• cba

总共有 3! = 6 种。

排列问题广泛应用于回溯算法训练、全排列生成、密码学暴力破解、组合优化问题、字符串变换问题及面试算法题等场景。在实际工程中，字符串排列常见于自动生成测试用例、排列搜索路径、游戏组合系统及全量枚举场景。

需求

基础需求

实现函数 Permutation(s string) []string，功能包括返回字符串所有排列、支持 Unicode、时间复杂度 O(n!)、使用回溯实现。

增强需求

• 若字符串包含重复字符，去除重复排列
• 提供非递归版本
• 支持大规模数据控制
• 提供字典序排列

代码规范要求

• 所有代码放在一个代码块中
• 不同文件使用注释分隔
• 代码必须包含详细中文注释
• 必须包含 main 测试

技术原理

1. 排列数量公式

若字符串长度为 n，排列数 = n!。

n	排列数
3	6
4	24
5	120
10	3628800

⚠ 排列增长极快，属于指数级复杂度。

2. 回溯算法原理

核心思想：选择 → 递归 → 撤销选择。

步骤：

1. 选择一个字符
2. 标记为已使用
3. 递归处理剩余字符
4. 回退（撤销标记）

3. 去重原理

若字符串包含重复字符，例如 "aab"，普通回溯会产生重复结果。

解决方案：排序 + 同层去重。

条件：if i > 0 && chars[i] == chars[i-1] && !used[i-1]

4. 时间复杂度

• 生成排列：O(n!)
• 空间复杂度：O(n)（递归栈）

实现思路

基础排列算法步骤

1. 转为 rune 切片
2. 创建 used 数组
3. 创建路径数组
4. 回溯函数：
   • 若路径长度等于 n → 加入结果
   • 遍历所有字符
   • 若未使用 → 选择
   • 递归
   • 撤销选择

去重版本步骤

1. 排序字符
2. 添加剪枝逻辑

代码实现

// ============================================= // 文件：main.go // =============================================
 main

 (
	
	
)



 [] {
	runes := [](s)
	n := (runes)
	 result []
	used := ([], n)
	path := ([], , n)

	
	 backtrack 
	backtrack =  {
		
		 (path) == n {
			result = (result, (path))
			
		}
		
		 i := ; i < n; i++ {
			 used[i] {
				
			}
			
			used[i] = 
			path = (path, runes[i])
			
			backtrack()
			
			path = path[:(path)]
			used[i] = 
		}
	}
	backtrack()
	 result
}


 [] {
	runes := [](s)
	sort.Slice(runes,   {
		 runes[i] < runes[j]
	})
	n := (runes)
	 result []
	used := ([], n)
	path := ([], , n)

	 backtrack 
	backtrack =  {
		 (path) == n {
			result = (result, (path))
			
		}
		 i := ; i < n; i++ {
			 used[i] {
				
			}
			
			 i >  && runes[i] == runes[i] && !used[i] {
				
			}
			used[i] = 
			path = (path, runes[i])
			backtrack()
			path = path[:(path)]
			used[i] = 
		}
	}
	backtrack()
	 result
}


 {
	fmt.Println()
	res1 := Permutation()
	 _, v :=  res1 {
		fmt.Println(v)
	}
	fmt.Println()
	res2 := PermutationUnique()
	 _, v :=  res2 {
		fmt.Println(v)
	}
}