Shulou(Shulou.com)06/01 Report--

In this article, the editor introduces in detail "the method of calculating the combination sum of the php backtracking algorithm". The content is detailed, the steps are clear, and the details are handled properly. I hope that this article "the method of calculating the combination sum of the php backtracking algorithm" can help you solve your doubts.

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

Each number in candidates can only be used once in each combination.

Description

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

Example

Enter:

Candidates = [10Perry 1, 2, 7, 6, 1, 5], target = 8

The solution set is:

[

[1, 7]

[1, 2, 5]

[2, 6]

[1, 1, 6]]

Problem-solving ideas

Refer directly to the cluster extinction permutation / combination / subset problem of backtracking algorithm.

Code class Solution {/ * @ param Integer [] $candidates * @ param Integer $target * @ return Integer [] [] * / public $res = []; function combinationSum2 ($candidates, $target) {sort ($candidates); / / sort $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); / / the number cannot be reused and requires + 1 array_pop ($array);}}

Instance expansion:

After reading this, the article "the method of calculating the sum of combinations by php backtracking algorithm" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself. If you want to know more about related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.