列表

详情


NC232. 加起来和为目标值的组合(三)

描述

找出所有相加之和是 n 的 k 个数的组合。组合中只含有 1~9的正整数,且保证每种组合中不含有相同的数字。
保证一定有解。结果按字典序升序输出。


示例1

输入:

3,7

输出:

[[1,2,4]]

示例2

输入:

2,3

输出:

[[1,2]]

示例3

输入:

2,5

输出:

[[1,4],[2,3]]

原站题解

import java.util.*;
public class Solution {
/**
*
*
*
* @param k int
* @param n int
* @return int
*/
public int[][] combination (int k, int n) {
// write code here
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++ 解法, 执行用时: 3ms, 内存消耗: 304KB, 提交时间: 2021-12-18

class Solution {
public:
/**
*
*
*
* @param k int
* @param n int
* @return intvector<vector<>>
*/
vector<vector<int>> ans;
vector<vector<int> > combination(int k, int n) {
// write code here
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);
/*for(auto iter=sub.begin();iter!=sub.end();iter++){
dict.erase(iter);
}*/
}
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:
/**
*
*
*
* @param k int
* @param n int
* @return intvector<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) {
// write code here
vector<int>list;
dfs(list,k,n,1);
return kk;
}
};

C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-07-13

class Solution {
public:
/**
*
*
*
* @param k int
* @param n int
* @return intvector<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) {
// write code here
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:
/**
*
*
*
* @param k int
* @param n int
* @return intvector<vector<>>
*/
vector<vector<int> > combination(int k, int n) {
// write code here
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:
/**
*
*
*
* @param k int
* @param n int
* @return intvector<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;
}
}
};

上一题