字符串的全排列
- 给定 1,2,3
- 输出：
1，2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
其实是一个树形结构
【】
1 2 3
2 3 1 3 1 2
123 132 213 231 312 321
使用深度优先搜索 DFS
- 深度 depth
- 走过路径 path
- 已经走过 used
- 每次走完一条路径则 记录下来
- 每次回溯 撤下上次的操作
可以看到 每次选择的路径的过程是一致的
- 可以使用递归
- 递归的退出是 depth 到最后
整个代码
点击查看代码
$num = 1;
function dfs($str, $len, $depth, $path, $used)
{
// 深度已经结束退出选择
if ($depth == $len) {
global $num;
echo $num++, " ", var_export(join('',$path)), PHP_EOL;
return ;
}
// 创建 条件分支 递归分支
for ($i = 0; $i < $len; $i++) {
// 标记已经选择的数字
if ($used[$i]) {
continue;
}
//入栈
array_push($path, $str[$i]);
$used[$i] = true;
// 递归选择
dfs($str, $len, $depth + 1, $path, $used);
// 回溯 撤下上一次选择
array_pop($path);
$used[$i] = false;
}
}
$str = "abc";
dfs($str, strlen($str),0,[],[]);