93. 递归实现组合型枚举

93. 递归实现组合型枚举

if (sum + n - u < m) return;

如果当前记录的数据 加上 后面的所有可以被选的数据 时无法达到要求时终止

state记录了哪些数据被选，哪些没被选的

state | 1 << u 选择当前的数据，比如0101 -> 10101

#include <iostream>
using namespace std;int n, m;
void dfs(int u, int sum, int state)
{if (sum + n - u < m) return;if (sum == m){for (int i = 0; i < n; i ++ )if (state >> i & 1) cout << i + 1 << " ";cout << endl;return;}dfs(u + 1, sum + 1, state | 1 << u);dfs(u + 1, sum, state);
}int main()
{cin >> n >> m;dfs(0, 0, 0);return 0;
}