赞
踩
题目:
题解:
- class Solution {
- private:
- vector<vector<int>> res;
- void backtracking(int k, int n, vector<int> ans){
- if(k == 0 || n <= 0){
- if(k == 0 && n == 0){
- res.emplace_back(ans);
- }
- return;
- }
- int start = (ans.size() == 0 ? 0 : ans.back()) + 1;
- for(int i = start; i < 10; i++){
- if(n - i < 0)break; // 加上元素i已经超过n,更大的i也就无须枚举了
- ans.emplace_back(i);
- backtracking(k - 1, n - i, ans);
- ans.pop_back();
- }
- }
- public:
- vector<vector<int>> combinationSum3(int k, int n) {
- if(n < (k + 1) * k / 2 || n > (19- k) * k / 2)return res;
- vector<int> ans;
- backtracking(k, n, ans);
- return res;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。