- Combination Sum III
Medium
1519
61
Add to List
Share
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.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.
Example 4:
Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.
Example 5:
Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
There are no other valid combinations.
Constraints:
2 <= k <= 9
1 <= n <= 60
我的解法
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<bool> num_mask(9, true);
vector<vector<int>> ret = recurr_search(k, n, num_mask);
return ret;
}
vector<vector<int>> recurr_search(int k, int n, vector<bool>& num_mask) {
vector<vector<int>> ret;
if (k <= 0) {
ret = {{}};
}
else if (k == 1) {
for (int i=0; i<9; ++i) {
if (num_mask[i] == true and i+1 == n) {
ret.emplace_back(vector<int>{i+1});
}
}
}
else {
vector<bool> num_mask_ = num_mask;
for (int i=0; i<9; ++i) {
if (num_mask[i] == true) {
num_mask[i] = false;
for (const auto& ret_from_recurr : recurr_search(k-1, n-i-1, num_mask)) {
vector<int> temp{i+1};
temp.insert(temp.end(), ret_from_recurr.begin(), ret_from_recurr.end());
ret.emplace_back(temp);
}
num_mask[i] = true;
}
num_mask[i] = false; // mark 1
}
num_mask = num_mask_; // mark 2
}
return ret;
}
};
Runtime: 4 ms, faster than 35.70% of C++ online submissions for Combination Sum III.
Memory Usage: 7.1 MB, less than 29.37% of C++ online submissions for Combination Sum III.
一开始考虑的是用unordered_set，但是想了想还是用vector<bool>比较方便，set没法O(1) random access。
然后concatenate两个vector一开始不知道，查了一下要用insert
https://stackoverflow.com/a/3177254/9556578
This is precisely what the member function std::vector::insert is for
std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());
还有一个小bug，ret.emplace_back(vector<int>{i+1});和ret.push_back({i+1});可以通过，但是ret.emplace_back({i+1});不可以
https://stackoverflow.com/questions/51443319/why-is-emplace-back-failing-even-though-the-direct-constructor-works
还有2个问题是关于mask的修改，为了避免重复，必须在mark1的位置要加false，但是这样每次子循环结束都会导致num_mask被完全false掉，导致没有下一个子循环了，所以在mark2的位置要复原成原mask
https://zxi.mytechroad.com/blog/searching/leetcode-216-combination-sum-iii/
其实没必要用mask，搜索的时候因为没有重复，所以可以从上次搜到的数的后一个开始
// Author: Huahua
// Runtime: 0 ms
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> cur;
dfs(k, n, 1, cur, ans);
return ans;
}
private:
// Use k numbers (>= s) to sum up to n
void dfs(int k, int n, int s,
vector<int>& cur, vector<vector<int>>& ans) {
if (k == 0) {
if (n == 0) ans.push_back(cur);
return;
}
for (int i = s; i <= 9; ++i) {
if (i > n) return;
cur.push_back(i);
dfs(k - 1, n - i, i + 1, cur, ans);
cur.pop_back();
}
}
};
我默写的答案：
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> curr;
dfs(k, n, 0, curr, ans);
return ans;
}
void dfs(int k, int n, int start, vector<int>& curr, vector<vector<int>>& ans) {
if (n < 0) return;
if (n == 0 and k == 0) {
ans.emplace_back(curr);
return;
}
for (int i=start; i<9; ++i) {
curr.emplace_back(i+1);
dfs(k-1, n-i-1, i+1, curr, ans);
curr.pop_back();
}
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum III.
Memory Usage: 6.8 MB, less than 58.74% of C++ online submissions for Combination Sum III.
注意，dfs里面的k n start都不能加引用，因为是k-1, n-i-1, i+1, 0都是rvalue
除非这么写：
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> curr;
dfs(k+0, n+0, 0, curr, ans);
return ans;
}
void dfs(int&& k, int&& n, int&& start, vector<int>& curr, vector<vector<int>>& ans) {
if (n < 0) return;
if (n == 0 and k == 0) {
ans.emplace_back(curr);
return;
}
for (int i=start; i<9; ++i) {
curr.emplace_back(i+1);
dfs(k-1, n-i-1, i+1, curr, ans);
curr.pop_back();
}
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum III.
Memory Usage: 6.5 MB, less than 91.93% of C++ online submissions for Combination Sum III.
网友评论