在本篇文章里小编给大家整理的是一篇关于php回溯算法计算组合总和的实例代码，有需要的朋友们可以学习参考下。

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字（包括目标数）都是正整数，解集不能包含重复的组合。

实例

输入:

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

所求解集为:

1. [ 
2. [1, 7], 
3. [1, 2, 5], 
4. [2, 6], 
5. [1, 1, 6]] 

解题思路

直接参考回溯算法团灭排列/组合/子集问题。

代码：

1. class Solution { 
2.     /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */ 
3.     public $res = []; 
4.     function combinationSum2($candidates, $target) { 
5.         sort($candidates);   // 排序 
6.         $this->dfs([], $candidates, $target, 0); 
7.         return $this->res; 
8.     } 
9.     function dfs($array, $candidates, $target, $start) { 
10.         if ($target < 0) return; 
11.         if ($target === 0) { 
12.             $this->res[] = $array; 
13.             return; 
14.         } 
15.         $count = count($candidates); 
16.         for ($i = $start; $i < $count; $i++) { 
17.             if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue; 
18.             $array[] = $candidates[$i]; 
19.             $this->dfs($array, $candidates, $target - $candidates[$i], $i + 1);//数字不能重复使用,需要+1 
20.             array_pop($array); 
21.     }} 

实例扩展：

1. <?php 
2. /* 
3.  * k = 2x + y + 1/2z 
4.  取值范围 
5.  * 0 <= x <= 1/2k 
6.  * 0 <= y <= k 
7.  * 0 <= z < = 2k 
8.  * x,y,z最大值 2k 
9.  */ 
10. $daMi = 100; 
11. $result = array(); 
12. function isOk($t,$daMi,$result) 
13. {/*{{{*/ 
14.  $total = 0; 
15.  $hash = array(); 
16.  $hash[1] = 2; 
17.  $hash[2] = 1; 
18.  $hash[3] = 0.5; 
19.  for($i=1;$i<=$t;$i++) 
20.  { 
21.  $total += $result[$i] * $hash[$i]; 
22.  } 
23.  if( $total <= $daMi) 
24.  { 
25.  return true; 
26.  } 
27.  return false; 
28. }/*}}}*/ 
29. function backtrack($t,$daMi,$result) 
30. {/*{{{*/ 
31.  //递归出口 
32.  if($t > 3) 
33.  { 
34.  //输出最优解 
35.  if($daMi == (2 * $result[1] + $result[2] + 0.5 * $result[3])) 
36.  { 
37.   echo "最优解，大米:${daMi},大牛：$result[1],中牛： $result[2]，小牛：$result[3]\n"; 
38.  } 
39.  return; 
40.  } 
41.  for($i = 0;$i <= 2 * $daMi;$i++) 
42.  { 
43.  $result[$t] = $i; 
44.  //剪枝 
45.  if(isOk($t,$daMi,$result)) 
46.  { 
47.   backtrack($t+1,$daMi,$result); 
48.  } 
49.  $result[$t] = 0; 
50.  } 
51. }/*}}}*/ 
52. backtrack(1,$daMi,$result); 
53. ?>

Tags: php回溯算法 php计算组合

分享到：