3ms c++ DP


  • 0
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            vector<int> sortedNums(nums);
            sort(sortedNums.begin(), sortedNums.end());
            vector<int> results(target + 1, 0);
            results[0] = 1;
            for (int i = 1; i <= target; i++) {
                for (int j = 0; j < sortedNums.size() && sortedNums[j] <= i; j++) {
                    results[i] += results[i - sortedNums[j]];
                }
            }
            return results[target];
        }
    };
    

  • 0
    H

    neat solution, but you can add a judgement to make it faster.
    '''
    int combinationSum4(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<int> res(target+1, 0);
    res[0] = 1;
    for(int i = 0; i < target+1; ++i){
    for(int j = 0; j < nums.size(); ++j){
    if(i >= nums[j]){
    res[i] += res[i-nums[j]];
    }
    else{
    break;
    }
    }
    }
    return res[target];
    }
    '''


  • 0

    Thank you for your reply, but I think our solutions are the same right? I put the judgement in the loop conditional statement.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.