📝 题目大意

给定一个整数 $N$（$0 \le N \le 21$），按字典序从小到大输出所有满足 $x + y + z \le N$ 的非负整数三元组 $(x, y, z)$。

💡 解题思路

1. 题目分析：$N$ 最大仅为 $21$，即使三重循环枚举所有可能的 $(x, y, z)$，最坏情况下也只需枚举 $O(N^3) \approx 10^4$ 种情况，完全在时限内。因此直接暴力枚举即可。

2. 算法推导：

   • 最外层循环枚举 $x$（代码中为 i），范围 $0 \sim N$。
   • 第二层循环枚举 $y$（代码中为 j），范围 $0 \sim N - x$（即 i + j <= n），因为 $x + y$ 已经不能超过 $N$。
   • 第三层循环枚举 $z$（代码中为 k），范围 $0 \sim N - x - y$（即 i + j + k <= n）。
   • 三层循环的嵌套顺序天然保证了字典序：先固定 $x$ 更小的，再固定 $y$ 更小的，最后 $z$ 从小到大，完全符合字典序的定义。

3. 边界与细节：

   • $N = 0$ 时，只输出 0 0 0。
   • 注意第二层和第三层循环的终止条件用的是 i + j <= n 和 i + j + k <= n，而不是 j <= n 和 k <= n，这样可以提前剪枝，避免枚举无效的三元组。
   • 输出时每行三个整数用空格分隔，末尾换行。

⏱️ 复杂度分析

• 时间复杂度：$O(N^3)$。合法三元组共有 $C_{N+3}^{3} = \frac{(N+3)(N+2)(N+1)}{6}$ 个，当 $N=21$ 时约为 $2024$ 个，远小于 $21^3 = 9261$。
• 空间复杂度：$O(1)$，仅使用了常数个变量。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n; scanf("%d", &n);
	// 最外层枚举 x，天然保证字典序：x 小的先输出
	for(int i = 0; i <= n; i++)
	{
		// 第二层枚举 y，满足 x + y <= n（剪枝）
		for(int j = 0; i + j <= n; j++)
		{
			// 第三层枚举 z，满足 x + y + z <= n
			for(int k = 0; i + j + k <= n; k++)
			{
				// 三个数三层循环，直接判断合法并输出
				printf("%d %d %d\n", i, j, k);
			}
		}
	}
	return 0;
}