目录
一、题目
1、题目描述
2、接口描述
python3
cpp
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
python3
cpp
一、题目
1、题目描述
找出所有相加之和为
n
的k
个数的组合,且满足下列条件:
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
2、接口描述
python3
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
cpp
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
}
};
3、原题链接
216. 组合总和 III
二、解题报告
1、思路分析
考虑暴搜,选或不选,这个很简单
然后考虑剪枝:
优化搜索顺序:优先选大的,这样路径少
可行性剪枝:
如果剩下的元素和加上当前元素和小于n,那么剪枝
如果剩下元素个数加上当前路径长度小于k,那么剪枝
2、复杂度
时间复杂度:
暴搜就不要管这个了不会算空间复杂度:emm
3、代码详解
python3
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
ret = []
path = []
def dfs(cur: int, s: int) -> None:
if not cur:
if s == n and len(path) == k:
ret.append(path.copy())
return
if len(path) + cur < k:
return
if s + (cur + 1) * cur // 2 < n:
return
dfs(cur - 1, s)
path.append(cur)
dfs(cur - 1, s + cur)
path.pop()
dfs(9, 0)
return ret
cpp
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ret;
vector<int> path;
function<void(int, int)> dfs = [&](int cur, int s){
if(!cur){
if(s == n && path.size() == k) ret.emplace_back(path);
return;
}
if(path.size() + cur < k) return;
if(s + (cur + 1) * cur / 2 < n) return;
dfs(cur - 1, s);
path.emplace_back(cur);
dfs(cur - 1, s + cur);
path.pop_back();
};
dfs(9, 0);
return ret;
}
};