How to calculate combined sum using backtracking algorithm in PHP-PHP Problem-php.cn

How to calculate combined sum using backtracking algorithm in PHP

醉折花枝作酒筹

Release： 2023-03-11 13:42:01

Original

1862 people have browsed it

Given an array of candidates and a target number target, find all the combinations in candidates that can make the sum of the numbers be target. What should we do at this time? Today I will take you through it.

How to calculate combined sum using backtracking algorithm in PHP

Given an array candidates and a target number target, find all the combinations in candidates that can make the sum of the numbers target. Each number in

candidates can only be used once in each combination.

Note:

All numbers (including the target number) are positive integers. The solution set cannot contain duplicate combinations.

Example 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:[
 [1, 7],
 [1, 2, 5],
 [2, 6],
 [1, 1, 6]]

Copy after login

Example 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:[  
[1,2,2],  
[5]]

Copy after login

Solution ideas

Direct reference to the backtracking algorithm group elimination permutation/combination/subset problem

Code

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);
        }
    }}

Copy after login

Extra:

Given a non-repeating element An array of candidates and a target number target, find all the combinations in candidates that can make the sum of numbers be target. The numbers in

candidates can be selected repeatedly without limit.

The difference is that repeated selections are allowed, and it is solved by making two changes based on the previous question.

class Solution {
    /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */
    public $res = [];
    function combinationSum($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
            array_pop($array);
        }
    }}

Copy after login

Extra:

Find all k combinations of numbers whose sum is n. Only positive integers from 1 to 9 are allowed in the combination, and there are no duplicate numbers in each combination.

Limit the number of elements in the selected scheme

class Solution {
    public $res = [];
    /** * @param Integer $k * @param Integer $n * @return Integer[][] */
    function combinationSum3($k, $n) {
        $this->dfs([], [1,2,3,4,5,6,7,8,9], $n, 0, $k);
        return $this->res;
    }
    function dfs($array, $candidates, $n, $start, $k) {
        if ($n < 0) return;
        if ($n === 0 && count($array) === $k) {
            $this->res[] = $array;
            return;
        }
        for ($i = $start; $i < 9; $i++) {
            if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue;
            $array[] = $candidates[$i];
            $this->dfs($array, $candidates, $n - $candidates[$i], $i + 1, $k);
            array_pop($array);
        }
    }}

Copy after login

Recommended learning: php video tutorial

The above is the detailed content of How to calculate combined sum using backtracking algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!