Combination Sum

发表于 | 分类于

Combination Sum

题目描述：

给定一个目标值，以及表示累加和数字的个数k。要求得到找到1-9中k个数为目标值的所有可能，要求结果中不存在重复值，且各个数字只能用一次。

例子：

给定k=3,target=7，则结果为[[1,2,4]];给定k=3,target=9,则结果为[[1,2,6],[1,3,5],[2,3,4]],见LeetCode216

解题思路：

首先已知我们只能用1-9的数，所以用过的数不能再次使用。这样相当于构建一棵树，新的节点的可能只能在上一个节点较大值中取。例如我们当前取值了5，则下一个节点的可能值只有6，7，8，9。基于以上事实，我们使用回溯的算法，在不断寻找的过程中，如果条件不满足则返回，如果满足题意则加入到结果中。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res; // 保存返回结果
        vector<int> record;   // 保存当前遍历结果
        dfs(res, k, n, record); //其中用k保存已经使用几个数
        								// n表示我们还需要多少满足目标值
        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;
        // 如果当前的遍历结果是空则从0开始
        // 否则从当前遍历结果中最后一个数的下一个数开始寻找
        for (int i = start; i <= 9; i++){
            record.push_back(i); // 将当前遍历值加入遍历结果
            dfs(res, k - 1, n - i, record); // 递归寻找
            record.pop_back();   // 回溯一步不然record里面会不断添加所有遍历过的数
        }
    }
};