组合（combination）

前天有人在群里问了一个问题：求长度为n的元素不重复数组中取m个元素相乘后的和。刚看到这个问题的时候我没有细想，有空之后想了一下，发现这是一个组合的问题，下面举个栗子。

在集合{1, 2, 3}中取出1，2，3个元素相乘，然后求和，那么计算方式如下

1个元素：（1）+（2）+（3）
2个元素：（1 × 2）+（1 × 3）+（2 × 3）
3个元素：（1 × 2 × 3）

以上3种情况。
很明显，这就是组合C的情况，从长度为n的集合中取出m个不重复的元素。
求组合利用公式我们很容易知道：

A = n (n-1) (n-2) ... (n-m+1) = （排列公式）
C = = = = C（组合公式）

但是题目需要计算组合积的和，所以我们需要找出所有组合情况。

下面先来找解题思路，再写代码，以集合{1, 2, 3}求C为例。（数学不够好，描述的不够精炼，请见谅）
要怎么解决这个问题呢？
1、取两个数，顺序去看这个集合，1设置为true（组合中存在）

image.png

ps：整数代表这个数在集合中存在，负数代表不存在。

2、然后往后面的元素走，看第二个元素，2设置为true。

image.png

3、这个时候够两个元素了，不用在此基础上往后面找了。

4、这个时候我们会跳过一个上一级组合中最后被设置为true的元素，把它设置为false，继续往后面查找，在这里这个元素是2。

image.png

5、现在不足2个元素，后面还有没看的元素，继续往下查找，接下来设置3为true。

image.png

后面则重复上面的步骤，最后完成的图的这样的：

image.png

灵魂画师画歪了，ignore it

这里有3个终点，就是总共有3种组合情况：

{1，2}，{1，3}，{2，3}

让我们再把那些不符合的情况也列出来：

image.png

ps：学过离散数学或者数据结构的同学应该知道，这其实是一个二叉树（具体是什么二叉树，就要问我那本已经尘封的数据结构了o(╯□╰)o）

其实到这里思路就已经比较清晰了，这是一种递归的做法，停止递归的条件是当前路线中的组合元素数量已经达到要求，或者目前的元素已经是最后一个元素（这里可以的逻辑可以优化一下，即改为即使后面的元素全部都include进来，也不能达到数量要求），下面就来写代码。

    /**
     * [getPowerByLength description]
     * @param  array  $source [源数组]
     * @param  array  &$val   [当前处理的集合]
     * @param  [type] $length [需要长度]
     * @return [type]         [description]
     */
    function getPowerByLength(array &$source, array $val, int $length, int $offset = 1) :void {
        global $powerSet;
        $nums = count($source);
        if ($length <= 0 || $length > $nums) {
            return;
        }elseif ($length == $nums) {
            $powerSet = [$source];
            return;
        }

        $count = count($val);
        if ($count == $length) {
            // 数量达标则停止
            $powerSet[] = $val;
            return;
        }elseif (($nums - $offset + 1 + $count) < $length) {
            // 剩余元素不足则停止
            return;
        }elseif ($offset > $nums) {
            // 到达最后一个元素则停止
            return;
        }
        // 往下查找
        // 设置false
        getPowerByLength($source, $val, $length, $offset + 1);
        // 设置true
        $val[] = $source[$nums - $offset];
        getPowerByLength($source, $val, $length, $offset + 1);
    }

    $array = [1, 2, 3, 4, 5];
    $powerSet = [];
    getPowerByLength($array, [], 4);
    var_dump($powerSet);

这里的代码是从数组尾部开始查找，所以结果会是倒序的。

这期就这么多了，希望对大家有所帮助。（不懂得怎么收尾总结，拜拜~）