📝 题目大意

在 $1 \sim M$ 中选出 $N$ 个数构成严格递增序列，按字典序输出所有方案。

💡 解题思路

1. 题目分析：

   • $N \leq M \leq 10$，数据范围极小，可以暴力枚举/回溯。
   • 严格递增的序列等价于从 $M$ 个元素中选出 $N$ 个的组合 $C(M,N)$，输出所有组合即可。
   • 要求字典序输出：先按第一位从小到大，第一位相同时按第二位从小到大，依此类推。

2. 算法推导：

   • 使用 DFS + 回溯 枚举所有组合。
   • dfs(start, depth) 含义：当前要选第 depth 个元素（从 0 计数），可选的起始值为 start。
   • 递归边界：当 depth == N 时，已经选够 $N$ 个数，输出序列并返回。
   • 递归过程：枚举 i 从 start 到 M，将 i 加入序列，然后递归调用 dfs(i + 1, depth + 1)——因为序列要严格递增，下一位必须从 i+1 开始选。递归返回后回溯（pop_back()），尝试更大的数。
   • 字典序自然保证：由于 DFS 中 i 从小到大枚举，且先探索小数字开头的分支，天然满足字典序要求。这与常规的组合枚举完全一致。

3. 边界与细节：

   • $N = M$ 时只有一种方案：[1, 2, ..., N]。
   • $N = 1$ 时直接输出 $1$ 到 $M$ 各一行。
   • 输出格式：数字之间用空格分隔，行末也可有空格（Sample 中有），每行一个序列。

⏱️ 复杂度分析

• 时间复杂度：$O\left(\binom{M}{N} \cdot N\right)$，共有 $C(M,N)$ 种方案，每种输出耗时 $O(N)$。最坏情况 $M=10$ 时组合数不超过 $C(10,5)=252$，完全可行。
• 空间复杂度：$O(N)$，递归栈深度为 $N$，加上存储序列的 vector。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;

int N, M;
vector<int> seq; // 存储当前枚举的序列

// start: 当前位置可选的最小值
// depth: 已经选了多少个数
void dfs(int start, int depth) {
    // 递归边界：选够了 N 个数，输出序列
    if (depth == N) {
        for (int i = 0; i < N; i++) {
            if (i > 0) cout << " "; // 数字间用空格分隔
            cout << seq[i];
        }
        cout << endl;
        return;
    }
    // 枚举当前位候选值，为保证递增，下一位从 i+1 开始
    for (int i = start; i <= M; i++) {
        seq.push_back(i);          // 选择 i
        dfs(i + 1, depth + 1);     // 递归下一位（必须严格递增）
        seq.pop_back();             // 回溯，撤销选择
    }
}

int main() {
    cin >> N >> M;
    dfs(1, 0); // 从 1 开始选，当前已选 0 个
    return 0;
}