最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

用Backtracking思想解决subset/permutation/combination/partition问题

XAMPP下载 admin 660浏览 0评论

这两天专门训练了backtracking类型的问题,包括N皇后、全排列全组合等等,我到现在也无法完全清晰描述recursive里的运行过程,但是多做了几道这种类型的题目之后发现还是很有套路的,即使思路不是很清晰也可以“凑”出代码。
recursive的代码有两点关键:1.出口条件 2.循环的写法

出口条件:出口条件还是挺容易,如全排列中list的长度为nums的length就把它加入到result list中,比如combination中sum等于target
循环的写法:
1.全排列中用for (int i = 0; i < mums.length; i ++), 全组合中用for (int i = index; i < mums.length; i ++),用一个visited数组来记录元素是否被访问过,if (visited[I] == true) continue;
2.如何处理有重复的情况?首先均需经过sort的预处理,全组合去除重复组合的写法: if (i > index && nums[i] == nums[i-1]) continue; 全排列去除重复组合的方法:if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false) continue;

转载请注明:XAMPP中文组官网 » 用Backtracking思想解决subset/permutation/combination/partition问题

您必须 登录 才能发表评论!