如何用php回溯算法计算组合总和
本篇内容主要讲解“如何用php回溯算法计算组合总和”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何用php回溯算法计算组合总和”吧!
创新互联公司专业为企业提供庄河网站建设、庄河做网站、庄河网站设计、庄河网站制作等企业网站建设、网页设计与制作、庄河企业网站模板建站服务,10余年庄河做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
所有数字(包括目标数)都是正整数。 解集不能包含重复的组合。
实例
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]
解题思路
直接参考回溯算法团灭排列/组合/子集问题。
代码
class Solution { /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */ public $res = []; function combinationSum2($candidates, $target) { sort($candidates); // 排序 $this->dfs([], $candidates, $target, 0); return $this->res; } function dfs($array, $candidates, $target, $start) { if ($target < 0) return; if ($target === 0) { $this->res[] = $array; return; } $count = count($candidates); for ($i = $start; $i < $count; $i++) { if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue; $array[] = $candidates[$i]; $this->dfs($array, $candidates, $target - $candidates[$i], $i + 1);//数字不能重复使用,需要+1 array_pop($array); } }}
到此,相信大家对“如何用php回溯算法计算组合总和”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
文章题目:如何用php回溯算法计算组合总和
本文URL:http://pwwzsj.com/article/gogjis.html