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

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());//排序，方便枚举每一段
        dfs(candidates, 0, target);
        return ans;
    }

    void dfs(vector<int>& candidates, int u, int target) {
        if (target == 0) {
            ans.push_back(path);
            return;
        }

        if (u == candidates.size()) return;

        //找到每一段的起始
        int k = u + 1;
        while (k < candidates.size() && candidates[k] == candidates[u]) k++;
        int cnt = k - u;//每一段有cnt个相同的数，枚举的个数不能超过cnt

        //枚举一下当前的数可以选几个,可以选0个，或者选i个总和不超过target的个数并且不能超过cnt个
        for (int i = 0; i * candidates[u] <= target && i <= cnt; i++) {
            dfs (candidates, k, target - i * candidates[u]);
            path.push_back(candidates[u]);
        }

        //恢复现场
        for (int i = 0; i * candidates[u] <= target && i <= cnt; i++) {
            path.pop_back();
        }
    }
};