• 技术文章 >PHP >PHP教程

    php回溯算法计算组合总和的方法

    小妮浅浅小妮浅浅2021-07-13 17:20:12转载362

    给定一个数组 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学习指路:php教程

    本文转载于php中文网,如有侵犯联系作者修改。

    专题推荐:php回溯算法
    品易云
    上一篇:php字符串相加的方法 下一篇:php正则去除内容中的图片

    相关文章推荐

    • php变量的引用赋值使用• php中的四种标量类型• php变量中的两种复合类型• php变量有哪些特殊类型• php定义常量方法的区别• php常量和变量的不同• php中DateTime的错误处理• php中unset函数的使用• php使用array_diff去除元素• php计算汉明距离总和的方法• php数据流中第K大元素的计算方法• php中rewrite如何理解• php8.1进入Alpha阶段,版本更新速看• php文件系统是什么• php字符串相加的方法

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网