dfs n选m c++模板

DFS（深度优先搜索）求解n选m问题，其中n是待选择的元素数量，m是需要选择的元素数量。c是用于存储已选择元素的数组。

C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int N = 20;  // 最大元素数量
int n, m;
vector<int> c;  // 存储已选择的元素

void dfs(int cur, int cnt) {  // cur表示当前需要选择的元素，cnt表示已经选择了cnt个元素
    if (cnt == m) {  // 已选择m个元素，输出答案
        for (int i = 0; i < m; i++) {
            cout << c[i] << " ";
        }
        cout << endl;
        return;
    }
    if (cur == n + 1) {  // 已经选完了所有元素
        return;
    }

    // 选择当前元素
    c.push_back(cur);
    dfs(cur + 1, cnt + 1);
    c.pop_back();  // 恢复现场

    // 不选择当前元素
    dfs(cur + 1, cnt);
}

int main() {
    cin >> n >> m;
    dfs(1, 0);  // 从第一个元素开始选择，已选择0个元素
    return 0;
}

Python代码实现：

n, m = map(int, input().split())
c = []

def dfs(cur, cnt):
    if cnt == m:
        for i in range(m):
            print(c[i], end=" ")
        print()
        return
    if cur == n + 1:
        return

    # 选择当前元素
    c.append(cur)
    dfs(cur+1, cnt+1)
    c.pop()  # 恢复现场

    # 不选择当前元素
    dfs(cur+1, cnt)

dfs(1, 0)  # 从第一个元素开始选择，已选择0个元素

时间复杂度为O(2^n)，因为每一个元素都有选或不选两种选择方式。空间复杂度为O(m)，因为需要存储已选元素的数组。