DFS-Recall7

发表于 分类于 ，

题目描述[原题连接][https://leetcode-cn.com/problems/combination-sum-iii/]

找出所有相加之和为 n 的k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

算法分析

​ 从1-9一次为开头进行dfs,当当前的向量vec长度为k的时候，计算当前向量中所有值的和，判断是否等于目标值n相等就加入到结果集ans中，直到遍历遍历到数字9结束，返回结果集；

C++代码

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>> vec;
     void dfs(vector<int> &v,int n,int k,int t){
        if(v.size()==k){
            int sum=0;
            for(int i=0;i<k;i++)
                sum+=v[i];
            if(sum==n)
                vec.push_back(v);
            return;
        }
         for(int i=t;i<=9;i++){
             v.push_back(i);
             dfs(v,n,k,i+1);
             v.pop_back();
         }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> v;
        dfs(v,n,k,1);
        return vec;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        traceBack(k, n, 0, 1, new LinkedList<>());
        return ans;
    }
    
    public void traceBack(int k, int n, int sum, int begin, LinkedList<Integer> list) {
        if(k == 0) {
            if(n == sum)
                ans.add(new ArrayList<>(list));
            return;
        }
        for(int i = begin; i < 10; i++) {
            list.add(i);
            traceBack(k - 1, n, sum + i ,i + 1, list);
            list.removeLast();
        }
    }
}