回溯算法是以深度优先搜索解的方法，以前还不是很熟悉递归，不过今天仔细想了想递归回溯搜索解确实是个简单快速的求解方法，就是有时候想的有点烧脑...
题目：给出abcd...这些字母求他们的全部排列组合
这个实际上用matlab自带的perms函数一下就能求解一个全排列矩阵，然后把1,2,3...这些数用a,b,c...字母代替就行，不过那样复杂度就大了，毕竟没有原生为字母排列的函数，那么用回溯法递归求解该问题matlab可编写如下：
function result = abcPerms(n)
result.count = 0;
result.cell = {};
result = traceback(result, \'\', 0:n-1);
function result = traceback(result, cur, arr)
base = abs(\'a\');
if isempty(arr)
result.count = result.count + 1;
result.cell{result.count} = cur;
disp(cur);
return;
end
for i = 0:length(arr)-1
result = traceback(result, [cur,char(base+arr(i+1))], arr(~(arr==arr(i+1))));
end
end
end
如执行abcPerms(3)即可得到结果：
>> abcPerms(3)
abc
acb
bac
bca
cab
cba
ans =
包含以下字段的 struct:
count: 6
cell: {\'abc\' \'acb\' \'bac\' \'bca\' \'cab\' \'cba\'}
请发表评论