首页 > 其他 > 详细

全排列

时间:2016-12-12 22:36:02      阅读:182      评论:0      收藏:0      [点我收藏+]

技术分享

[1,2,3,4]的全排列,可以看作1和[2,3,4]全排列,[1,2]和[3,4]全排列。。。。因此可以用递归解决。

在每次扩展中,将未出现的元素不断加入,且在这个过程中,不需要保存路径

void dfs_permutation(vector<int>& num,vvi& result,vi& path)
{
    if(num.size()==path.size())//出口
    {
        result.push_back(path);
        return;
    }

    for(auto i:num)
    {
        auto pos = find(path.begin(),path.end(),i);
        if(pos==path.end())//如果该元素不在path中,加入
        {
            path.push_back(i);
            dfs_permutation(num,result,path);
            path.pop_back();//要将该元素弹出
        }
    }
}
vvi Permutation(vi num)
{
    vvi result;
    vi path;
    dfs_permutation(num,result,path);
    return result;
}

 

全排列

原文:http://www.cnblogs.com/573177885qq/p/6165724.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!