题目描述

算法1

(DFS) $O(2^n)$

T(n) = T(n-1) + T(n-2) + T(n-2) …
T(n-1) = T(n-2)+T(n-3)… use this to replace T(n-1) in the above,
so T(n) = 2 * [ T(n-2) + T(n-3) ], and so on, T(n) = O(2^n))

C++ 代码

class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> combination;
        combinationSum3(n, res, combination, 1, k);
        return res;
    }
private:
    void combinationSum3(int target, vector<vector<int> > &res, vector<int> &combination, int begin, int need) {
        if (!target) {
            res.push_back(combination);
            return;
        }
        else if (!need)
            return;
        for (int i = begin; i != 10 && target >= i * need + need * (need - 1) / 2; ++i) {
            combination.push_back(i);
            combinationSum3(target - i, res, combination, i + 1, need - 1);
            combination.pop_back();
        }
    }
};

算法2

Python 代码

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        self.dfs(list(range(1, 10)), k, n, [], res)
        return res

    def dfs(self, nums, k, n, path, res):
        if k < 0 or n < 0:
            return 
        if k == 0 and n == 0:
            res.append(path)
        for i in range(len(nums)):
            self.dfs(nums[i+1:], k-1, n-nums[i], path+[nums[i]], res)