Combination Sum III

发表于 | 分类于

Combination Sum III

题目描述：

给定数组[1…..9]和数字k，要求返回数组中k个数和为n的所有组合。

例子：

具体描述见LeetCode216

解题思路：

主要的解题思路是深度优先搜索。我们用res保存最后的结果，用record保存当前访问过程的结果，k表示还需要访问数的个数，n表示剩余的和。当k和n都等于0的时候，把当前的访问结果保存下来；不符合的情况我们直接返回；而后需要确定继续下一层遍历的起始位置，我们需要判断当前的record是否为空，为空置为1，不为空置为尾部数据的下一个数即可。而后继续遍历。需要注意的地方在于我们push到record中后，当前深度优先搜索结束后需要pop出当前层push的数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> record;
        dfs(res, k, n, record);
        return res;
        
    }
    void dfs(vector<vector<int>>& res, int k, int n, vector<int>& record){
        if (k == 0 && n == 0){
            res.push_back(record);
            return;
        }
        if (n <= 0 || k == 0)
            return;
        int start = record.size() == 0 ? 1 : record.back() + 1;
        for (int i = start; i <= 9; i++){
            record.push_back(i);
            dfs(res, k - 1, n - i, record);
            record.pop_back();
        }
    }
};