博文中会简要介绍Leetcode P0216题目分析及解题思路。
“Combination Sum III”和p0040一样也是p0039的一道衍生题。这道题的思路也比较简单，我们可以使用深度优先搜索，这里利用递归回溯的思想。
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.
由于我们是在1-9中任选k个数，并且这k个数不能有重复，所以我们需要维护一个lower即当前选择下的最小值即可，上界则不超过9。同时我们维护一个sum来记录当前所有选择的数的和，再维护一个数组combination来记录我们选择的数，然后每次选择一个数以后更新sum和数组combination并进入下一次选择，直到sum和指定目标相等并且数组combination中的元素个数恰好是k时，我们记录下当前所有数形成的组合。
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
this.dfs(1, 0, n, k, new ArrayList<>());
return this.combinations;
}
private List<List<Integer>> combinations = new ArrayList<>();
private void dfs(int lower, int sum, int N, int K,
List<Integer> combination) {
int count = combination.size();
if (count == K) {
if (sum == N)
this.combinations.add(new ArrayList<>(combination));
return;
}
for (int num=lower; num<10; ++num) {
combination.add(num);
this.dfs(num+1, sum+num, N, K, combination);
combination.remove(count);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> combination;
this->_Dfs(1, 0, n, k, combination);
return this->combinations_;
}
private:
vector<vector<int>> combinations_;
void _Dfs(int lower, int sum, int N, int K,
vector<int> &combination) {
int count = combination.size();
if (count == K) {
if (sum == N)
this->combinations_.push_back(vector<int>(combination));
return;
}
for (int num=lower; num<10; ++num) {
combination.push_back(num);
this->_Dfs(num+1, sum+num, N, K, combination);
combination.pop_back();
}
}
};