有一组数字[0,1,2,3,4,5,6,7,8,9],现给出一个数字,比如3,
要求从该组数字中选出相加等于3的组合(相加的数字3个),如0+0+3=3,0+1+2,3个相加的数字不能相同(如1+1+1就不行),无顺序要求。
大概函数是这样 fun(数组,和值,3) ,得到的是组合的个数.
参数3是相加的数字个数,这里规定是3,如0+0+3,这是3个数字
有一组数字[0,1,2,3,4,5,6,7,8,9],现给出一个数字,比如3,
要求从该组数字中选出相加等于3的组合(相加的数字3个),如0+0+3=3,0+1+2,3个相加的数字不能相同(如1+1+1就不行),无顺序要求。
大概函数是这样 fun(数组,和值,3) ,得到的是组合的个数.
参数3是相加的数字个数,这里规定是3,如0+0+3,这是3个数字
请参考以下 python 代码实现
# -*- coding: utf-8 -*-
"""
author: 李毅
"""
from unittest import TestCase
def permutation(array, nsum):
''' 假设数组元素不重复。 '''
# 排序(升序)
sarray = sorted(array)
# 找出最大下标
max_idx = len(sarray)
for i, e in enumerate(sarray):
if e > nsum:
max_idx = i
break
# 穷举
result = []
for i in range(max_idx):
for j in range(i, max_idx):
for k in range(j, max_idx):
if i == j and j == k:
continue
if sarray[i] + sarray[j] + sarray[k] == nsum:
result.append((sarray[i], sarray[j], sarray[k]))
return result
class Test(TestCase):
""" 单元测试 """
def test_permutation(self):
self.assertEqual(
permutation(range(10), 3),
[(0, 0, 3), (0, 1, 2)])
self.assertEqual(
permutation(range(10), 2),
[(0, 0, 2), (0, 1, 1)])
# 边界值
self.assertEqual(
permutation(range(3), 3),
[(0, 1, 2)])
self.assertEqual(
permutation(range(1, 4), 4),
[(1, 1, 2)])
<?php
/**
* @title
* @author start2004
* @since 2018/5/10
*/
/**
* 有一组数字[0,1,2,3,4,5,6,7,8,9],现给出一个数字,比如3,
* 要求从该组数字中选出相加等于3的组合(相加的数字3个),如0+0+3=3,0+1+2,3个相加的数字不能相同(如1+1+1就不行),无顺序要求。
* 大概函数是这样 fun(数组,和值,3) ,得到的是组合的个数.
* 参数3是相加的数字个数,这里规定是3,如0+0+3,这是3个数字
* https://segmentfault.com/q/1010000014767442?utm_source=tag-newest
*/
ini_set('memory_limit', '8M');
$arr = [0,1,2,3,4,5,6,7,8,9];
$sum = 2;
$num = 3;
$resultArray = calc($arr, $sum, $num);
//var_dump($resultArray);
/**
* @title 入口函数
* @param array $arr
* @param int $sum
* @param int $num
* @return array
*/
function calc($arr = [], $sum = 0, $num = 0){
$resultArray = main($arr, $sum, $num);
$listArray = [];
if($resultArray){
foreach ($resultArray as $rArray){
/**
* num>1
* 不能所有值一样
* 去重后,数组长度大于1
*/
if ($num=1 OR (array_unique($rArray)) > 1){
/**
* 数组排序,去重返回
*/
sort($rArray);
if (in_array($rArray, $listArray) === false){
$listArray[] = $rArray;
echo implode(" + ", $rArray), " = {$sum}", PHP_EOL;
}
}
}
}
/**
* 没有符合条件
*/
if (empty($listArray)){
echo "sum = {$sum}, num = {$num}, no result.", PHP_EOL;
}
return $listArray;
}
/**
* @title 执行函数
* @param array $arr
* @param int $sum
* @param int $num
* @param array $feed
* @return array|bool
*/
function main($arr = [], $sum = 0, $num = 0, $feed = []){
if($num < 1){
return false;
} elseif($num == 1){
/**
* num=1,最后一个值是leftSum,且必须在arr中
*/
if(in_array($sum, $arr) !== false){
$feed[] = $sum;
echoLine($sum, $sum, 0, $feed);
return [$feed];
} else {
return false;
}
} else {
$listArray = [];
foreach ($arr as $val){
/**
* 只要小于sum,就执行递归
*/
if($val <= $sum){
$leftSum = $sum-$val;
$leftNum = $num-1;
$leftFeed = array_merge($feed, [$val]);
echoLine($val, $leftSum, $leftNum, $leftFeed);
$resultArray = main($arr, $leftSum, $leftNum, $leftFeed);
if($resultArray){
foreach ($resultArray as $rArray){
$listArray[] = $rArray;
}
}
}
}
return $listArray;
}
}
/**
* @title 递归视图输出
* @param $key
* @param $sum
* @param $num
* @param $feed
*/
function echoLine($key, $sum, $num, $feed){
return ;
$prefix = str_repeat("│ ", count($feed)-1);
echo $prefix;
echo "├─key={$key}";
if($num>0){
echo ", sum={$sum}, num={$num}";
}
echo PHP_EOL;
}
/**
├─key=0, sum=2, num=2
│ ├─key=0, sum=2, num=1
│ │ ├─key=2
│ ├─key=1, sum=1, num=1
│ │ ├─key=1
│ ├─key=2, sum=0, num=1
│ │ ├─key=0
├─key=1, sum=1, num=2
│ ├─key=0, sum=1, num=1
│ │ ├─key=1
│ ├─key=1, sum=0, num=1
│ │ ├─key=0
├─key=2, sum=0, num=2
│ ├─key=0, sum=0, num=1
│ │ ├─key=0
*/
10 回答11.1k 阅读
15 回答8.4k 阅读
7 回答5.2k 阅读
6 回答6.9k 阅读✓ 已解决
6 回答3k 阅读
5 回答4.8k 阅读✓ 已解决
4 回答3k 阅读✓ 已解决
递归查找符合规则的元素集合: