The method of calculating combinatorial Sum by php backtracking algorithm
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.
