首页 > 代码库 > 构造增量法生成子集

构造增量法生成子集

题意:

生成 1~n 集合的子集, 先按元素从小到大再按字典序排列输出

分析:

所谓构造增量法, 就是每次都输出当前数组的元素, 然后再给当前数组最大元素一个增量, 看是否仍然在集合内, 如果在就把他继续放进数组, 输出。 这种方法不需要显式确认递归边界, 如果无法添加元素, 自然就不会再递归了。 数据结构我选用了string , 因为字典序比较容易排序出来。

#include <bits/stdc++.h>
using namespace std;
string ans[1 << 15  + 5];
int A[10];
int cnt = 0;
void print_subset(int n, int* A, int cur){
    for(int i = 0; i < cur; i++)
    {
       ans[cnt] += A[i] + 0;
    }
    cnt++;
    int s = cur ? A[cur-1] + 1 : 1;// 确定已选元素的最大可能值
    for(int i = s; i <= n; i++){
        A[cur] = i;
        print_subset(n, A, cur + 1); // 递归构造子集
    }
}
bool cmp(string a, string b){
    if(a.size() < b.size())
        return true;
    else if(a.size() == b.size()){
        return a < b;
    }
    else return false;
}
int main() {
  int n;
  while(scanf("%d", &n) != EOF){
      cnt = 0;
      print_subset(n, A, 0);
      sort(ans, ans + cnt, cmp);
      cout << 0 <<endl;
      for(int i = 1; i < cnt; i++){
         cout << ans[i].size() <<" " << ans[i][0] - 0;
         for(int j = 1; j < ans[i].size(); j++){
            cout <<" " << ans[i][j] - 0;
         }
         ans[i] = "";
         cout << "\n";
      }
      printf("\n");
  }
  return 0;
}

 

构造增量法生成子集