https://tijs3pw2i8g.feishu.cn/docx/KBJude34oouSQcxyXHRcVYXKndg

组合问题

77 组合

https://leetcode.cn/problems/combinations/
u(startIndex)用来记录下一层递归时，搜索的起始位置（防止出现重复的组合）
一个集合求组合时，用u(startIndex)
dfs(nums, u)表示不可以重复取nums中的元素，dfs(nums, u + 1)表示可以重复取nums中的元素
分析树枝去重 or 树层去重：树层去重要对nums重新排序，树枝去重要用used(st)数组判断是否使用过

class Solution {
public:
    vector<vector<int>> res; 
    vector<int> path; 

    void dfs(int n, int k, int u) {
        if(path.size() == k) {
            res.push_back(path); 
            return; 
        }

        for(int i = u; i <= n; i ++) {   // 这里可以做一个剪枝优化
            path.push_back(i); 
            dfs(n, k, i + 1); 
            path.pop_back(); 
        }
    }

    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1); 
        return res; 
    }
};

216 组合总和3

https://leetcode.cn/problems/combination-sum-iii/

class Solution {
public:
    vector<vector<int>> res; 
    vector<int> path; 

    void dfs(int n, int k, int sum, int u) {
        if(sum > n)     return;     // 剪枝
        if(sum == n && path.size() == k) {
            res.push_back(path); 
            return; 
        }

        for(int i = u; i <= 9; i ++) { // 这也可以剪枝
            sum += i; 
            path.push_back(i); 
            dfs(n, k, sum, i + 1); 
            sum -= i; 
            path.pop_back(); 
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(n, k, 0, 1); 
        return res; 
    }
};