递归求子集算法 通俗解释

说明

我目前初学算法，所以语言上应该会比算法大佬们通俗很多。考虑到方便性，我使用的伪代码为基于 php 加上一些自然语言处理的代码，可以比直接写 C++ 代码更容易理解。文章末尾会附上我的 C++ 代码。

原理分析

首先看原理。

现有集合 set = [1, 2, 3] 。设有一个空集 setToAppend = [] 。

挑出 set[0] = 1 。

向 setToAppend 添加 1 或不添加 1 ，可得到两个集合 [1] 与 [] 。

[]
 +-- []
 +-- [1]

挑出 set[1] = 2 。

向刚才生成的两个集合中的 [1] 添加 2 或不添加 2 ，可得到两个集合 [1, 2] 与 [1] 。

向刚才生成的两个集合中的 [] 添加 2 或不添加 2 ，可得到两个集合 [2] 与 [] 。

[]
 +-- []
     +--[2]
     +--[]
 +-- [1]
     +--[1, 2]
     +--[1]

对于产生的四个集合，再分别添加 3 或不添加 2 ，可得到八个集合：

[]
+-- []
    +-- [2]
        +-- [2, 3]
        +-- [2]
    +-- []
        +-- [3]
        +-- []
+-- [1]
    +-- [1, 2]
        +-- [1, 2, 3]
        +-- [1, 2]
    +-- [1]
        +-- [1, 3]
        +-- [1]

这八个集合就是 [1, 2, 3] 的所有子集了：

[2, 3],
[2],
[3],
[],
[1, 2, 3],
[1, 2],
[1, 3],
[1]

这就是子集生成的原理。那么如何转写为代码呢？

参数分析与伪代码表述

首先看涉及到哪些变量。

1. 集合 set = [1, 2, 3] 。
2. 当前的下标 index 。
3. 被追加的集合 setToAppend （也就是一开始的空集）
4. 生成的集合 setGenerated （也就是之后被追加的集合）

所以我们设计一个函数 subset：

function subset($set, $index = 0, $setToAppend = [], $setGenerated = []){

}

然后怎么做？回顾我们的自然语言表述：

挑出 set[0] = 1 。

向 setToAppend 添加 1 或不添加 1 ，可得到两个集合 [1] 与 [] 。

翻译成伪代码：

function subset($set, $index = 0, $setToAppend = [], $setGenerated = null){
    $numberToAdd = $set[$index]; // 要用于添加的数字

    $generatedSet1 = $setToAppend; // 产生的第一个集合
    $generatedSet2 = $setToAppend.append($numberToAdd); // 产生的第二个集合
}

由于我们把生成的两个集合分别对待，所以参数中的 $setGenerated 相当于分开写了。可以删掉。

function subset($set, $index = 0, $setToAppend = []){
    // ...    
}

接下来，要针对生成的两个集合，再执行一次生成操作：

function subset($set, $index = 0, $setToAppend = []){
    // ...（之前的代码）
    $index++; // 由于生成用的数字是下一位，所以索引自增了。
    $setToAppend1 = $generatedSet1;
    $setToAppend2 = $generatedSet2;    
    // 由于生成了两个集合，所以两个都要分别继续生成
    subset($set, $index, $setToAppend1);
    subset($set, $index, $setToAppend2);
}

现在差不多了，还缺少的就是终止条件。我们可以注意到，如果 $index 自增之后，超出了 $set 的范围，也即 $set.size == $index 时，就应该中止了。根据之前的分析，最后生成的集合就是真正的子集了：

function subset($set, $index = 0,  $setToAppend = []){
    if($set.size == $index){
        print($setToAppend) // setToAppend 也就是之前生成的集合 generatedSet。
        return;
    }
    // ...（之前的代码）
}

考虑到要将结果存放起来，我们可以增加一个引用传值的参数，用来存放结果。

function subset(&$result, $set, $index = 0,  $setToAppend = []){
    if($set.size == $index){
        $result.append($setToAppend) // setToAppend 也就是之前生成的集合 generatedSet。
        return;
    }
    // ...
}

现在程序的全貌是这样的：

function subset(&$result, $set, $index = 0,  $setToAppend = []){
    if($set.size == $index){
        $result.append($setToAppend) // setToAppend 也就是之前生成的集合 generatedSet。
        return;
    }
    $numberToAdd = $set[$index]; // 要用于添加的数字

    $generatedSet1 = $setToAppend; // 产生的第一个集合
    $generatedSet2 = $setToAppend.append($numberToAdd); // 产生的第二个集合

    $index++; // 由于生成用的数字是下一位，所以索引自增了。

    $setToAppend1 = $generatedSet1;
    $setToAppend2 = $generatedSet2;    
    // 由于生成了两个集合，所以两个都要分别继续生成
    subset($result, $set, $index, $setToAppend1);
    subset($result, $set, $index, $setToAppend2);    
}

现在，转写为编程语言吧。

编程语言表述

/**
 * 输出一个集合的所有子集
 */

#include <iostream>
#include <vector>

using namespace std;

template <class T>
void subsets(vector<vector<T>> &result, const vector<T> &originSet, size_t index, vector<T> setToAppend)
{
    if (originSet.size() == index)
    {
        if (setToAppend.size() >= 0)
        {
            result.push_back(setToAppend);
        }
        return;
    }

    vector<T> setToAppend1 = setToAppend;
    setToAppend.push_back(originSet[index]);
    vector<T> setToAppend2 = setToAppend;

    index++;

    subsets(result, originSet, index, setToAppend1);
    subsets(result, originSet, index, setToAppend2);
}

template <class T>
void printSet(vector<vector<T>> set)
{
    cout << "set: " << endl;
    for (size_t i = 0; i < set.size(); i++)
    {
        vector<T> subset = set[i];
        cout << "{";
        for (size_t j = 0; j < subset.size(); j++)
        {
            cout << subset[j];
            if (j != subset.size() - 1)
            {
                cout << ", ";
            }
        }
        cout << "}" << endl;
    }
}

int main()
{
    vector<vector<int>> result;
    subsets(result, {1, 2, 3, 4, 5, 6, 7, 8, 9}, 0, {});
    printSet<int>(result);
    return 0;
}