Leetcode 216. Combination Sum III（python+cpp）

题目

解析：

这题其实可以用39几乎一样的解法，只需要加个当前数组的长度判断就阔以了。到这里，可以对比permutation I,II; combination; combination I,II,II对比放到一起看，在我写的博客里都有，看完这些应该这类题就可以掌握了
python代码如下：

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:def back_tracking(first,comb):if len(comb)==k and sum(comb)==n:ans.append(comb[:])returnif sum(comb)>n:returnfor i in range(first,10):comb.append(i)back_tracking(i+1,comb)comb.pop()ans = []back_tracking(1,[])return ans

C++版本如下：

class Solution {
    
public:vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> ans;vector<int> curr;back_tracking(1,curr,0,ans,k,n);return ans;}
void back_tracking(int first,vector<int> curr,int currsum,vector<vector<int>>& ans,int k, int n){
    if (currsum==n && curr.size()==k){
    ans.push_back(curr);return;}if (currsum>n) return;for (int i=first;i<=9;++i){
    curr.push_back(i);back_tracking(i+1,curr,currsum+i,ans,k,n);curr.pop_back();}}
};