回望法求解子集

回溯法求解子集

C/C++ code

 求n个元素集合的子集，如A = {1, 2, 3}则A集合的子集有:    P(A) = {{1,2,3}, {1,2}, {1,3},{1},{2,3},{2},{3},{}}  

C/C++ code

方法采用回溯 ，严蔚敏书上的提到的所谓状态图,其他方法 暂且不采用谢谢了啊

C/C++ code

# include<iostream># include<cstdio>using namespace std;const int N = 3;int data[N] = {1,2,3};const int maxdeep = 3;int used[N];int subset[N];void work(int deep ){    for(int i = 0 ; i < deep ; i ++)    {        printf("%d\t",subset[i]);    }    printf("\n");    if(deep >= maxdeep)        return ;    //    for(int i = deep ; i < N ; i ++){        if(used[i] == 0)        {            used[i] = 1;            subset[deep] = data[i];            work(deep + 1);            used[i] = 0; //这里就是回溯 ，如果我理解没错的化        }    }}int main(){    //生成非空子集    for(int i = 0 ; i < N  ; i ++){        used[i] = 1;        subset[0] = data[i];        work(1);    }    // 如果直接work(0) 那么就会生成全排列    return 0;}