C++ 解法, 执行用时: 3ms, 内存消耗: 304KB, 提交时间: 2021-12-18
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* k int整型
* n int整型
* int整型vector<vector<>>
vector<vector<int>> ans;
vector<vector<int> > combination(int k, int n) {
vector<int> dict(9);
for(int i=0;i<10;i++)
dict[i]=i+1;
vector<int> sub;
backtrace(dict,sub,0,0,k,n);
return ans;
}
void backtrace(vector<int>& dict,vector<int>& sub,int start,int cur,int k,int n){
if(cur>=n){
if(cur==n&&sub.size()==k){
ans.push_back(sub);
}
return;
}
for(int i=start;i<dict.size();i++){
sub.push_back(dict[i]);
backtrace(dict, sub, i+1, cur+dict[i], k, n);
sub.pop_back();
}
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-02-20
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* k int整型
* n int整型
* int整型vector<vector<>>
vector<vector<int>>kk;
void dfs(vector<int>&list,int k,int n,int h)
{
if(n<=0){if(n==0&&list.size()==k)kk.push_back(list);return ;}
for(int i=h;i<=9;i++)
{
list.push_back(i);
dfs(list,k,n-i,i+1);
list.pop_back();
}
}
vector<vector<int> > combination(int k, int n) {
vector<int>list;
dfs(list,k,n,1);
return kk;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-07-13
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* k int整型
* n int整型
* int整型vector<vector<>>
void insert(int k,vector<int>& v,int a,int b,vector<vector<int>>& vv)
{
if(v.size()==k&&a==0)
{
vv.push_back(v);
return;
}
if(a<0||v.size()>k||b>9)return;
for(int i=b;i<=9;++i)
{
v.push_back(i);
insert(k, v, a-i, i+1, vv);
v.pop_back();
}
}
vector<vector<int> > combination(int k, int n) {
vector<int>v;
vector<vector<int>>vv;
insert(k, v, n, 1, vv);
return vv;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-03-14
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
int cur_k = 0;
int cur_tar = 0;
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* k int整型
* n int整型
* int整型vector<vector<>>
vector<vector<int> > combination(int k, int n) {
if(n > 45){
return {};
}
vector<int> nums = {1,2,3,4,5,6,7,8,9};
dfs(nums, n, k, 0);
return res;
}
void dfs(vector<int>& nums, int n, int k, int cur_i){
if(cur_tar > n || cur_k > k){
return;
}
if(cur_tar == n && cur_k == k){
res.push_back(path);
return;
}
for(int i=cur_i; i<nums.size(); i++){
path.push_back(nums[i]);
cur_k += 1;
cur_tar += nums[i];
dfs(nums, n, k, i+1);
path.pop_back();
cur_k -= 1;
cur_tar -= nums[i];
}
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2021-12-18
class Solution {
public:
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* k int整型
* n int整型
* int整型vector<vector<>>
vector<vector<int> > combination(int k, int n) {
lst.resize(k);
serchCombin(k, n, 1);
return result;
}
private:
vector<vector<int> > result;
vector<int> lst;
int idx=0;
void serchCombin(int k, int n, int start) {
if(1==k) {
lst[idx]=n;
result.push_back(lst);
return;
}
--k;
for(int i=start;k*(i+1)<=(n-i);++i) {
lst[idx++]=i;
serchCombin(k, n-i, i+1);
--idx;
}
}
};