C 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-03-20

int combination(int* nums, int numsLen, int target ) {
    // write code here
    if (target == 0) {
        return 1;
    }
    int total = 0;
    for (int i = 0; i < numsLen; i++) {
        if (target - nums[i] >= 0) {
            total += combination(nums, numsLen, target - nums[i]);
        }
    }
    return total;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2021-12-31

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

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

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

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

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

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2021-12-16

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