首页 > 代码库 > 构造增量法生成子集
构造增量法生成子集
题意:
生成 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; }
构造增量法生成子集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。