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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

This topic created in 2064 days ago, the information mentioned may be changed or developed.

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 三种可能

谢谢

整数

加数

等于

可能

3 replies • 2020-09-13 15:47:46 +08:00

jingous

Sep 13, 2020

最简单的回溯法

jingous

Sep 13, 2020

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

Sep 13, 2020

完全背包方案数