C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-07-30

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param nums int整型vector
     * @return int整型vector<vector<>>
     */
    void findall(int target, vector<int>& nums, vector<vector<int>>& res,
                 vector<int>& temp, int pos, int sum) {
        if (sum >= target || pos >= nums.size()) {
            if (sum == target) {
                res.push_back(temp);
            }
            return;
        }
        for (int i = pos; i < nums.size(); i++) {
            temp.push_back(nums[i]);
            findall(target, nums, res, temp, i, sum + nums[i]);
            temp.pop_back();
        }
        return;
    }
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        // write code here
        vector<vector<int>> result;
        vector<int> temp;
        findall(target, nums, result, temp, 0, 0);
        return result;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-07-05

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    void dfs(vector<vector<int>>&res,int start,vector<int>&path, int target, vector<int>& nums){
        if(target==0){
            res.push_back(path);
            return ;
        }
        for(int i=start;i<nums.size();i++){
            if(nums[i]<=target){
                path.push_back(nums[i]);
                dfs(res, i, path, target-nums[i], nums);
                path.pop_back();
            }
        }
    }
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        vector<vector<int>>res;
        vector<int>path;
        sort(nums.begin(),nums.end());
        dfs(res, 0, path,  target, nums);//2^n
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-06-13

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        // write code here
        vector<vector<int>>v;
        if(nums.size()==0)
        {
            return v;
        }
        vector<int>temp;
        dsf(v,temp,nums,target,0);
        return v;
    }
    void dsf(vector<vector<int>>&v,vector<int>&temp,vector<int>& nums,int target,int index)
    {
        if(target==0)
        {
            v.emplace_back(temp);
            return;
        }
        if(target<0)
        {
            return;
        }
        for(int i=index;i<nums.size();i++)
        {
            temp.emplace_back(nums[i]);
            dsf(v,temp,nums,target-nums[i],i);
            temp.pop_back();
        }
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-24

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        // write code here
        vector<vector<int>> res;
        vector<int> track;
        int sum = 0;
        backtrack(nums, target, res, track, sum, 0);
        return res;
    }

private:
    void backtrack(vector<int> &nums, int &target, vector<vector<int>> &res, vector<int> &track, int &sum, int start) {
        int sz = nums.size();
        if (sum == target) {
            res.push_back(track);
        }
        if (sum > target) return;
        
        for (int i = start; i < sz; ++i) {
            sum += nums[i];
            track.push_back(nums[i]);
            backtrack(nums, target, res, track, sum, i);
            track.pop_back();
            sum -= nums[i];
        }
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-11

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combinationCount(int target, vector<int>& nums) {
        // write code here
        vector<vector<int>> res;
        vector<int> path;
        
        sort(nums.begin(), nums.end());
        dfs(res, path, 0, 0, target, nums);
        return res;
    }
    void dfs(vector<vector<int>>& res, vector<int>& path, int index, int cur_sum, int target, vector<int>& nums)
    {
        if(cur_sum == target)
        {
            res.push_back(path);
            return;
        }
        for(int i = index; i < nums.size() && cur_sum +nums[i] <= target; i++)
        {
            path.push_back(nums[i]);
            cur_sum += nums[i];
            dfs(res, path, i, cur_sum, target, nums);
            cur_sum -= nums[i];
            path.pop_back();
        }
    }
};