javascript - Given a value, such as 100, and an array, select N elements from the array. The sum of these N elements is also 100. Just get one result.

Such as array:

<code>var arr = [99.1, 92.2, 60, 50,
           49.5, 45.7, 25.1, 20, 
           17.4, 13, 10, 7, 2.1, 2, 1];
</code>

Find the array elements whose sum is 100:

<code>[60,20,10,7,2,1]
</code>

Reply content:

Such as array:

<code>var arr = [99.1, 92.2, 60, 50,
           49.5, 45.7, 25.1, 20, 
           17.4, 13, 10, 7, 2.1, 2, 1];
</code>

Find the array elements whose sum is 100:

<code>[60,20,10,7,2,1]
</code>

<code>function f($n, $arr) { //$n是目标数字，$arr是数字组成的数组
    if (empty($arr)) return false; //如果数组没有元素，返回
    if (in_array($n, $arr)) return [$n];//如果期望的值已经存在，直接返回这个值
    foreach($arr as $k => $v) { //遍历数组
        if ($v > $n) continue; //比指定数还大，过
        $copy = $arr; //复制数组
        unset($copy[$k]); //去掉复制数组中已经被选中的数字
        $next = f($n - $v, $copy); //递归计算
        if(! empty($next)) return array_merge([$v], $next); //合并结果集
    }
    return false;//没找到啊
}
$arr = [99.1, 92.2, 60, 50, 49.5, 45.7, 25.1, 20, 7.4, 13, 10, 7, 2.1, 2, 1];
$data = f(100, $arr);
print_r($data);//Array ( [0] => 60 [1] => 20 [2] => 13 [3] => 7 ) 
$data = f(105, $arr);
print_r($data);//Array ( [0] => 60 [1] => 20 [2] => 13 [3] => 10 [4] => 2 ) </code>

Let’s get a Python version:

<code>def subsetsum(elements, target):
    if target==0:
        return True, []
    elif not elements or target < 0:
        return False, None

    result, subset = subsetsum(elements[:-1], target-elements[-1])
    return (True, subset + [elements[-1]]) if result else subsetsum(elements[:-1], target)</code>

The idea is very simple. When I want to ask whether elements can be added to target, there are only two possibilities:

1. I need to use element[-1] to add target -> I need to be able to use elements[:-1] to add target-elements[-1]

2. I don’t need to use element[-1] to add target -> I need to be able to use elements[:-1] to add target

boundary condition is:

1. When target is 0, it means I can add it without using anything, so return True, []

2. When elements is empty or target is a negative value, it means it can never be added, so return False, None

---

Test:

<code>elements = [99.1, 92.2, 60, 50, 49.5, 45.7, 25.1, 20, 17.4, 13, 10, 7, 2.1, 2, 1]
target = 100
result, subset = subsetsum(elements, target)
print(result, subset)</code>

Result:

<code>True [60, 20, 10, 7, 2, 1]</code>

---

Off topic, I feel very familiar when I see this question. It would be more interesting if we also consider the speed of solution and so on.

I have done research in this area before, and I raised a question about transformation. You can think about it:

Today we are given a multiset of integers (it is ok to represent negative numbers) (a multiset is a set, but elements are allowed to appear repeatedly), called elements, and given another multiset of integers, it is called targets, let’s ask whether there are several sub-multisets, and the sum of elements of each sub-multiset has exactly one corresponding target in targets.

It’s okay if you don’t understand the definition. Let me give you an example:

<code>elements = (1,4,6,4,1)
targets = (5,10,1)</code>

This example has a solution:

<code>(1,4) -> 5
(4,6) -> 10
(1) -> 1</code>

Note that each element in elements can only be used once!

Composition problem. Take a look at the original title of leetcode:

<code>function t100(array){
  var tempArray = array.concat([]).sort(function(a,b){
    return a-b;
  });
  var temp = 0;
  var result = [];
  for(var i=0;i<tempArray.length;i++){
    if(tempArray[i]>100){
      tempArray.length = i;
    }
  }
  for(var i=0;i<tempArray.length;i++){
    temp+=tempArray[i];
    result.push(tempArray[i]); 
    if(temp==100){
      console.log("已经找到相加得100的数字们:",result)
      return result;
    }
    else{
      console.log("暂时没有计算出相加得100的数字们")      
    }
  }
}
t100([10,10,10,10,20,20,234,244,20,40]);</code>

A loop within a recursion