0301 递归实现指数型枚举

迈不过友情╰ 2022-01-22 03:29 197阅读 0赞

题目链接： [contest-hunter.org:83/contest/0x00「基本算法」例题/0301][contest-hunter.org_83_contest_0x00_0301] 递归实现指数型枚举

本题可以用一个递归思路解决。每一个数都有放或者不放两种状态。  
其实本题还可以用一个思路解决。一定有2^n种排列方案。所以可以通过位枚举来列举出所有的可能排列。

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    
    /*int n;
    int num[20];
    int hah[1 << 21];
    
    int lowbit(int x)
    {
        return x & (-x);
    }
    
    int check(int x) 
    {
        for(int i = 0; i <= 20; i ++)
        {
            hah[1 << i] = i;
        }
        return hah[x];
    }
    int main()
    {
        scanf("%d",&n);
        for(int i = 0; i < 20; i ++)
            num[i] = i;
        for(int i = 1; i < (1 << n); i ++)
        {
            int j = i;
            int mark = 1;
            while(j)
            {
                int ans = lowbit(j);
                int pos = check(ans) + 1;
                if(mark == 1)
                  {
                      printf("%d",num[pos]); mark = 0;
                  }
                else
                    printf(" %d",num[pos]);
                j = j & (~(1 << (pos - 1)));
            }
            printf("\n");
        }
        printf("\n");
    }*/
    vector<int>Q;
    int n;
    
    void dfs(int x)
    {
        if(x == n + 1)
        {
            int len = Q.size();
            for(int i = 0; i < len; i ++)
                if(i == 0)
                   printf("%d",Q[i]);
                else
                   printf(" %d",Q[i]);
            printf("\n");
            return ;
        }
        dfs(x + 1);
        Q.push_back(x);
        dfs(x + 1);
        Q.pop_back();
    }
    
    int main()
    {
        scanf("%d",&n);
        dfs(1);
    }

[contest-hunter.org_83_contest_0x00_0301]: http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0301