[数据结构与算法]LeetCode - 解题笔记 - 216 - Combination Sum III

Solution 1

本题是对 0040. Combination Sum II 的扩展，但借了 0077. Combination 的核心，即固定候选数字的个数且不放回，选择满足target的方案。

所以本题仍然是dfs搜索，但是使用 0077. Combination 的按尺寸的枚举方案，并且在深入过程中维护当前累加值acc和target的差距，并且在满足条件的终止条件同时判定枚举序列尺寸和acc与target的关系。

• 时间复杂度：$O((\genfrac{}{}{0ex}{}{n}{k})\times k)$，所有$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$中情形，注意这里的n是可用数字范围（本题是9）而非输入的n，每种需要k长度规模的遍历
• 空间复杂度：$O(n)$，temp数组最大占用为k，但是递归占用可能会达到n

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> temp;
        
        this->dfs(1, 9, k, n, 0, temp, ans);
        
        return ans;
    }
    
private:
    void dfs(int pos, int n, int k, int target, int acc, vector<int> & temp, vector<vector<int>> & ans) {
        // 这里的n是遍历数组的长度（本题始终为9），sum才是输入的n
        if (temp.size() + (n - pos + 1) < k) {
            return;
        }
        if (temp.size() == k && acc == target) {
            ans.emplace_back(temp);
            return;
        }
        
        if (pos == n + 1) {
            return;
        }
        
        temp.emplace_back(pos);
        dfs(pos + 1, n, k, target, acc + pos, temp, ans);
        temp.pop_back();
        dfs(pos + 1, n, k, target, acc, temp, ans);
    }
};

Solution 2

Solution 1的Python实现

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        temp = []
        
        self._dfs(1, 9, k, n, 0, temp, ans)
        
        return ans
        
    def _dfs(self, pos: int, n: int, k:int, target:int, acc:int, temp: List[int], ans: List[List[int]]) -> None:
        # 这里的n是遍历数组的长度（本题始终为9），sum才是输入的n
        if len(temp) + (n - pos + 1) < k:
            return
        
        if len(temp) == k and target == acc:
            ans.append(copy.deepcopy(temp))
            return
        
        if pos == n + 1:
            return 
        
        temp.append(pos)
        self._dfs(pos + 1, n, k, target, acc + pos, temp, ans)
        temp.pop()
        self._dfs(pos + 1, n, k, target, acc, temp, ans)