子集生成问题

分手后的思念是犯贱 2021-09-30 13:56 390阅读 0赞

/*#include<cstdio>
    #include<algorithm>
    using namespace std;
    void print_subset(int n,int* A,int cur){
    for(int i=0;i<cur;i++)printf("%d ",A[i]);
    printf("\n");
    int s=cur?A[cur-1]+1:0;
    for(int i=s;i<n;i++){
    A[cur]=i;
    print_subset(n,A,cur+1);
    }
    }
    int main(){
    int n,A[1000];
    scanf("%d",&n);
    print_subset(n,A,0)    ;
    return 0;
    } */
    #include<iostream> 
    #include<stdio.h> 
    #include<string.h>
    using namespace std; 
    int n; 
    int k1[10];//存放具体数据 
    int pos[10];//存放每次查找下一个元素的在集合k1中元素的具体位置 
    
    void add_cl (int cur)//从一定程度上，我们可以这么理解cur参数：即cur是我们进行图的遍历的层数 
    { 
    if(cur == 3) 
    { 
    for (int i=0;i<cur; i++) 
    { 
    cout<<k1[pos[i]]; 
    } 
    cout<<endl; 
    } 
    
    
    int dingwei = cur ? pos[cur-1] + 1 : 0; 
    
    
    //这句对于大多数人来说比较晦涩难懂，下面注释部分为这句的较为通俗的写法 
    //上面一句就是这个算法的核心------->> 我们的集合pos其实存放的数据是满足我们设置的一定条件的集合k1中的元素的具体位置 
    //我们通过一些条件控制到达了避过一部分已经找到的子集目的，有效的过滤了不满足条件的集合，增加了我们进行了递归操作的效率 
    
    /* 
    if (cur == 0) 
    { 
    dingwei = 0; 
    } 
    else 
    { 
    dingwei = pos[cur-1] + 1; 
    } 
    
    */ 
    for (int i=dingwei;i<n;i++) 
    { 
    pos[cur] = i; 
    add_cl(cur+1); 
    //这个算法的一个好处：我们不用特别的判断递归条件，因为我们进行的数组的遍历，我们通过循环无形中进行了控制， 
    //也就是说在此时这个for循环的工作空间内，进行了添加数据的操作，如果不满足这个for循环的条件，我们就可以这么认为：无法添加新的元素，自然也就不会有递归了 
    } 
    } 
    
    int main () 
    { 
    while (cin>>n) 
    { 
    memset(k1,0,sizeof(k1)); 
    memset(pos,0,sizeof(pos)); 
    for (int i=0;i<n;i++) 
    { 
    cin>>k1[i]; 
    } 
    add_cl (0); 
    } 
    return 0; 
    }

第一种是直接是从1到N的数的子集不需要存储位置，第二种是随便的几个数，不是连续自然数，所以需要记录位置。

参考：http://blog.csdn.net/ajfdlkasjgdlkas/article/details/53152721

转载于:https://www.cnblogs.com/ls-pankong/p/8510135.html