leetcode解题: Combination Sum III (216)

发表于 | 分类于

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

1
[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

1
[[1,2,6], [1,3,5], [2,3,4]]

解法1：

典型的backtracking的题目，用一般的模板就能解决。用一个helper函数，用一个数保存当前试的数的起始位置， 用一个vector存储当前选出的答案。
要注意的是退出条件。 同时注意到由于存在可能计算重复的数据，所以memorization可以帮助efficiency，不过下面的答案没有用。
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
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> temp;
        vector<vector<int>> res;
        int num = 1; 
        int max = 9;
        helper(temp, res, k, n, num, max);
        return res;
    }
    
    void helper(vector<int>& cur, vector<vector<int>>& res, int k, int n, int num, int max) {
        
        if (n < 0 || (k == 0 && n > 0) || (n == 0 && k != 0)) {
            return;
        }
        
        if (n == 0 && k == 0) {
            res.push_back(cur);
            return;
        }
        
        for (int i = num; i <= max; ++i) {
            cur.push_back(i);
            helper(cur, res, k - 1,n - i, i + 1, max);
            cur.pop_back();
        }
        
    }
};

Java

1