216. Combination Sum III(medium, backtrack, 本类问题做的最快的一次)

时间:2023-08-29 19:13:38

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

关于 backtrack problem 做的最快的一次.

定义了2个东西:

  • start
  • remain

自己想法,自己代码:

vector<vector<int>> combinationSum3(int k, int n) {
vector<int> A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector<vector<int> > res;
vector<int> temp;
backtrack(res, temp, A, k, 0, n);
return res;
} void backtrack(vector<vector<int> >& res, vector<int>& temp, vector<int>& A,
int k, int start, int remain) {
if (temp.size() == k && remain == 0) {
res.push_back(temp);
return;
}
for (int i = start; i < A.size(); i++) {
temp.push_back(A[i]);
backtrack(res, temp, A, k, ++start, remain - A[i]);
temp.pop_back();
}
}