[leetcode] Combination Sum III
5841 단어 BacktrackingarrayBacktracking
유의할점
문제 제대로 읽기
풀이
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;
}
};
Author And Source
이 문제에 관하여([leetcode] Combination Sum III), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@6047198844/Combination-Sum-III저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)