你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
func sum(array : [Int]) -> Int{
var sum = 0
array.forEach { (item) in
sum = item + sum
}
return sum
}
func susetNumbers(array :[Int], target : Int, subsetArray: [Int],result : inout [[Int]]) -> [[Int]]{
let s = sum(array: subsetArray)
if(s == target){
print("sum\(subsetArray) = \(target)")
result.append(subsetArray)
}
for i in 0..<array.count{
let n = array[i]
let remaning = Array(array[(i+1)..<array.count])
susetNumbers(array: remaning, target: target, subsetArray: subsetArray + [n], result: &result)
}
return result
}
var resultArray = [[Int]]()
let newA = susetNumbers(array: [1,2,3,4,5], target: 5, subsetArray: [],result:&resultArray)
print(resultArray)
其他回答
Thank you.. ephemient
我已经将上述逻辑从python转换为php..
<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;
print_r(bestsum($data,$maxsum)); //function call
function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array(); //base case
foreach($data as $group)
{
$new_res = $res; //copy res
foreach($group as $ele)
{
for($i=0;$i<($maxsum-$ele+1);$i++)
{
if($res[$i] != 0)
{
$ele_index = $i+$ele;
$new_res[$ele_index] = $res[$i];
$new_res[$ele_index][] = $ele;
}
}
}
$res = $new_res;
}
for($i=$maxsum;$i>0;$i--)
{
if($res[$i]!=0)
{
return $res[$i];
break;
}
}
return array();
}
?>
我不喜欢上面看到的Javascript解决方案。下面是我使用部分应用、闭包和递归构建的一个:
好的,我主要关心的是,如果组合数组能满足目标要求,希望这样你就能找到剩下的组合了
这里只需要设置目标并传递组合数组。
function main() {
const target = 10
const getPermutationThatSumT = setTarget(target)
const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])
console.log( permutation );
}
我提出的当前实现
function setTarget(target) {
let partial = [];
return function permute(input) {
let i, removed;
for (i = 0; i < input.length; i++) {
removed = input.splice(i, 1)[0];
partial.push(removed);
const sum = partial.reduce((a, b) => a + b)
if (sum === target) return partial.slice()
if (sum < target) permute(input)
input.splice(i, 0, removed);
partial.pop();
}
return null
};
}
c#版本的@msalvadores代码的答案
void Main()
{
int[] numbers = {3,9,8,4,5,7,10};
int target = 15;
sum_up(new List<int>(numbers.ToList()),target);
}
static void sum_up_recursive(List<int> numbers, int target, List<int> part)
{
int s = 0;
foreach (int x in part)
{
s += x;
}
if (s == target)
{
Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target);
}
if (s >= target)
{
return;
}
for (int i = 0;i < numbers.Count;i++)
{
var remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count;j++)
{
remaining.Add(numbers[j]);
}
var part_rec = new List<int>(part);
part_rec.Add(n);
sum_up_recursive(remaining,target,part_rec);
}
}
static void sum_up(List<int> numbers, int target)
{
sum_up_recursive(numbers,target,new List<int>());
}
另一个python解决方案是使用itertools.combination模块,如下所示:
#!/usr/local/bin/python
from itertools import combinations
def find_sum_in_list(numbers, target):
results = []
for x in range(len(numbers)):
results.extend(
[
combo for combo in combinations(numbers ,x)
if sum(combo) == target
]
)
print results
if __name__ == "__main__":
find_sum_in_list([3,9,8,4,5,7,10], 15)
输出:[(8,7),(5,10),(3,8,4),(3,5,7)]
我想我应该用这个问题的答案,但我不能,所以这是我的答案。它使用的是《计算机程序的结构和解释》中答案的修改版本。我认为这是一个更好的递归解,应该更能取悦纯粹主义者。
我的答案是用Scala(如果我的Scala很烂,我很抱歉,我刚刚开始学习)。findsumcombination的疯狂之处在于对递归的原始列表进行排序和惟一,以防止欺骗。
def findSumCombinations(target: Int, numbers: List[Int]): Int = {
cc(target, numbers.distinct.sortWith(_ < _), List())
}
def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = {
if (target == 0) {println(solution); 1 }
else if (target < 0 || numbers.length == 0) 0
else
cc(target, numbers.tail, solution)
+ cc(target - numbers.head, numbers, numbers.head :: solution)
}
使用它:
> findSumCombinations(12345, List(1,5,22,15,0,..))
* Prints a whole heap of lists that will sum to the target *