Combination Sum III - Medium - L
Published:
Question
- https://leetcode.com/problems/combination-sum-iii/
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Approach
- BackTracking
Solution
class Solution {
public:
vector<vector<int>>res;
vector<int>temp;
void find(int i,int k,int n)
{
if(k==0)
{
if(n==0)
{
res.push_back(temp);
}
return;
}
for(int j=i;j<=9;j++)
{
if(j<=n)
{
temp.push_back(j);
find(j+1,k-1,n-j);
temp.pop_back();
}
}
}
vector<vector<int>> combinationSum3(int k, int n)
{
find(1,k,n);
return res;
}
};