子集树算法文档

1.算法概述

子集树是一种 回溯算法，用于生成一个集合的所有子集。给定一个数组 arr，该算法递归地遍历所有可能的子集，并通过一个辅助数组 x 标记当前元素是否被选中。

2.算法特点

• 时间复杂度：O(2n)O(2n)（因为一个包含 n 个元素的集合有 2n2n 个子集）。

• 空间复杂度：O(n)O(n)（递归栈深度）。

• 适用场景：需要枚举所有子集的问题，如组合、子集和、幂集等。

3.代码实现

#include <iostream>
#include <string>

using namespace std;
void func(int arr[], int i, int length,int x[])
{
    if (i == length)//递归终止条件：处理完所有元素
    {
        for (int j = 0; j < length; j++)
        {
            if (x[j] == 1)//如果当前元素被选中，则输出
                cout << arr[j] << " ";
        }
        cout << endl;
    }
    else
    {
        x[i] = 1;//选择当前节点
        func(arr, i + 1, length,x);//处理左子树
        x[i] = 0;//不选择当前节点
        func(arr, i + 1, length,x);//处理右子树
    }
}
int main()
{
    int arr[] = { 1,2,3 };
    int length = sizeof(arr) / sizeof(int);
    int x[3] = { 0 };//初始化数组为0
    func(arr, 0, length,x);
    return 0;
}