LeetCode 216 组合总和III

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字最多使用一次

返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

本质上就是在9个数中选取k个数，要求k个数的和为n。

回溯递归实现

和组合问题类似，当前元素仅有两种状态，选或不选，进行简单的剪枝，当前值相加超过总和n或者当前元素值已经大于所需元素值则停止，元素不足时则停止的方式剪枝：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        DFS(1,k,n);
        return res;
    }
    void DFS(int cur,int k,int n){
        if(path.size()==k&&n==0){
            res.push_back(path);
            return;
        }
        if(n<0||cur>n) return;
        if(path.size()+(10-cur)<k) return;
        path.push_back(cur);
        n=n-cur;
        DFS(cur+1,k,n); // 第一次递归
        path.pop_back();
        n+=cur;
        DFS(cur+1,k,n); // 回溯后第二次递归
    }
};

注：将vector数组作为函数参数进行传递，将会导致传参时对参数进行复制，同时导致空间复杂度和时间复杂度的上升。

同时在本题中，使用的回溯递归方式为：选取当前字符进行递归，再不选取进行一次递归，这样递归的方式将会导致深度工作栈的深度更深，从到导致空间复杂度上升。此处要提升空间复杂度，修改为加大树的宽度，使用for循环实现。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        DFS(1,k,n);
        return res;
    }
    void DFS(int cur,int k,int n){
        if(path.size()==k&&n==0){
            res.push_back(path);
            return;
        }
        if(n<0||cur>n) return;
        if(path.size()+(10-cur)<k) return;
        for(int i=cur;i<=9;i++){
            path.push_back(i);
            n=n-i;
            DFS(i+1,k,n); // 第一次递归
            path.pop_back();
            n+=i;
        }
    }
};