请教算法题『要求和等于自然数 n，每个加数都必需是小于等于 k 的正整数，不限加数的数量，有多少钟可能』的思路
By Newyorkcity at 2020 年 9 月 13 日 · 1384 次点击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 条回复 • 2020-09-13 15:47:46 +08:00
 |
1
jingous 2020 年 9 月 13 日
最简单的回溯法
|
|
2
jingous 2020 年 9 月 13 日  1
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(); } } } }; |
 |
3
zxCoder 2020 年 9 月 13 日 1
完全背包方案数
|