请教算法题『要求和等于自然数 n，每个加数都必需是小于等于 k 的正整数，不限加数的数量，有多少钟可能』的思路
Newyorkcity · 2020-09-13 15:17:57 +08:00 · 647 次点击这是一个创建于 1318 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 三种可能
谢谢
 |
1
jingous 2020-09-13 15:37:27 +08:00
最简单的回溯法
|
|
2
jingous 2020-09-13 15:38:11 +08:00  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-09-13 15:47:46 +08:00 1
完全背包方案数
|
Select Language