881
遞歸求集合的所有子集的程序
#include <iostream>#include <vector>
using namespace std;
//算法描述:
//1、如果遍曆完全集，打印出所有被標記為true的元素
//2、否則：
//3、取第depth個元素，即標記為true
//4、繼續判斷第depth+1個元素
//5、不取第depth個元素，媽標記為false
//6、繼續判斷第depth+1個元素
//如：集合元素為a,b,c
// 把與元素a對應的標記為true,表示要取出
//判斷元素b，進入第一層遞歸，裏麵就標記b為取出，再進入遞歸，標記C為取出，再進入遞歸，打印a,b,c
//退出上一層遞歸，標記c不取出，進入第二個遞歸，由於已經遍曆完，打印出ab,
//依此類推
//。。。
void getAllSubset(char str[], int size, vector<bool> bVector, int depth);
int main()
{
char s[] = {'a', 'b', 'c'};
int size = sizeof(s) / sizeof(char);
vector<bool> v(size, false);
getAllSubset(s, size, v, 0);
return 0;
}
void getAllSubset(char str[], int size, vector<bool> bVector, int depth)
{
if (depth == size) //如果把size個數都判斷完，就把取出的數打印出來
{
for (int i = 0; i < size; i++)
{
if (bVector[i] != false)
cout << str[i] << " ";
}
cout << endl;
}
else
{
bVector[depth] = true; //取第de pth個數
getAllSubset(str, size, bVector, depth+1); //判斷第depth+1個數
bVector[depth] = false; //不取第depth個數
getAllSubset(str, size, bVector, depth+1); //判斷第depth+1個數
}
}
最後更新：2017-04-02 18:14:51