请教算法题『要求和等于自然数 n，每个加数都必需是小于等于 k 的正整数，不限加数的数量，有多少钟可能』的思路

[Newyorkcity]

k 一定是正整数

比如 n = 3, k = 3，有：

3 = 3

3 = 2 + 1 （ 3=1+2 是同一种可能）

3 = 1 + 1 + 1

三种可能。

如果 n = 3 k = 2 则只有：

3 = 2 +1

3 = 1 + 1 + 1 三种可能

---

谢谢

[jingous]

最简单的回溯法

[jingous]

class Solution {
public:
vector<vector<int>> SumEqualN(int n, int k) {
vector<vector<int>> res;
vector<int> tmp;
dfs(res,tmp,n,k,1,0);
return res;
}
void dfs(vector<vector<int>>& res, vector<int>& tmp, int n, int k, int idx, int sum){
if(sum == n){
res.push_back(tmp);
return ;
}
for(int i=idx; i<=k; ++i){
if(sum+i <= n){
tmp.push_back(i);
dfs(res,tmp,n,k,i,sum+i);
tmp.pop_back();
}
}
}
};

[zxCoder]

完全背包方案数