[leetcode] Combination Sum III

유의할점

문제 제대로 읽기

풀이

sum이 n보다 큰경우 . temp에 저장된 갯수가 원하는 갯수 k 보다 큰경우 → backtracking

크기가 k에 도달했을때, sum과 같을때 → 정답

크기가 k에 도달했을때, sum과 다름 → backtracking

코드

C++

class Solution {
private:
    vector<vector<int>> res;
public:
    void makeCombi(int k, int n,vector<int> &temp, int idx, int sum){
        if(sum > n||temp.size()>k){
            return;
        }
        
        if(sum == n){
            if(temp.size()==k)
                res.push_back(temp);
            return;
        }
        
        for(int i = idx; i <= 9; i++){
            temp.push_back(i);
            makeCombi(k, n,temp, i+1, sum+i);
            temp.pop_back();
        }
        
        return;
    }
    
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> temp;
        makeCombi(k,n,temp,1,0);
        return res;
    }
};