例题:递归实现组合型枚举

在子集枚举的基础上，进行剪枝

  1. vector<int> chosen;
  3. void dfs(int x)
  4. {
  5.     if (chosen.size() > m || chosen.size() + (n - x + 1) < m) return ;
  7.     if (x == n + 1)
  8.     {
  9.         //如何输出状态
  10.         for (int i = 0; i < chosen.size(); i++)
  11.             printf("%d ", chosen[i]);
  12.         puts("");
  14.         return ;
  15.     }
  17.     //选x
  18.     chosen.push_back(x);
  19.     dfs(x + 1);
  20.     chosen.pop_back();
  22.     //不选x
  23.     dfs(x + 1);
  24. }
  1. // 递归实现，枚举的时候带着顺序
  2. // get_combination(已经选了几个数，前一个选的是几)
  3. void get_combination(int u, int last)
  4. {
  5.     if (u == m){
  6.         for (int i = 0; i < m; i++) printf("%d ", chosen[i]);
  7.         puts("");
  8.     }
  10.     for (int j = last + 1; j <= n; j++){
  11.         chosen.push_back(j);
  12.         get_combination(u + 1, j);
  13.         chosen.pop_back();
  14.     }
  15. }
  17. // 调用get_combination(0, 0);
  1. //位运算版本，这是进阶的
  2. //state表示状态
  3. void dfs(int u, int sum, int state)
  4. {
  5.     if (sum > m || sum + n - u < m) return ;
  7.     if (sum == m)
  8.     {
  9.         for (int i = 0; i < n; i++)
  10.             if (state >> i & 1)
  11.                 cout << i + 1 << ' ';
  12.         puts("");
  14.         return ;
  15.     }
  17.     dfs(u + 1, sum + 1, state | 1 << u);
  18.     dfs(u + 1, sum    , state         );
  19. }