首页 > 代码库 > ACM:回溯法,子集生成
ACM:回溯法,子集生成
(一)增量构造法
#include <iostream> #include <algorithm> using namespace std; const int MAXN = 1000; int A[MAXN], n; void print_subset(int n, int *A, int cur) { for(int i = 0; i < cur; ++i) cout << A[i] << " "; cout << endl; int s = (cur ? A[cur-1]+1 : 0); //选取当前填到第cur个位置上的可以填的最小是数字! for(int i = s; i < n; ++i) { A[cur] = i; print_subset(n, A, cur+1); } } int main() { cin >> n; print_subset(n, A, 0); return 0; }
(二)位向量法
#include <iostream> #include <algorithm> using namespace std; const int MAXN = 1000; int B[MAXN], n; void print_subset(int n, int *B, int cur) { if(cur == n) { for(int i = 0; i < cur; ++i) { if(B[i]) cout << i << " "; } cout << endl; return ; } B[cur] = 1; //选第cur个元素 print_subset(n, B, cur+1); B[cur] = 0; //不选第cur个元素 print_subset(n, B, cur+1); } int main() { cin >> n; print_subset(n, B, 0); return 0; }必须当“所有元素是否选择”全部确定完毕后才是一个完整的子集。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。