DP C++ solution with clear explaination


  • 0
    C

    1Here is the thoughts. We start from nums[0], which the count is 1. (nums[0] itselft)

    Then we set the target number T is nums[0]+i.

    1. Assume we use one nums[0], so the new target number become T-nums[0] and we use DP to get the count of T-nums[0].
    2. Again, assume we use one nums[1], the new target number becom T-nums[1]....etc

    Finally, we reach the target numer!

    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            
            sort(nums.begin(), nums.end());
            if (nums.size() == 0 || target < nums[0])
                return 0;
                
            vector<int> count(target-nums[0]+1, 0);
            for (int i = 0 ; i < count.size() ; i++){
                int curTarget = i+nums[0];
                int j = 0;
                while(nums[j] <= curTarget && j < nums.size()){
                    int  left = curTarget - nums[j];
                    if (left >= nums[0]){
                        count[i] += count[left-nums[0]];
                    }
                    if (left == 0)
                        count[i]++;
                    j++;
                }
            }
           return count.back();
        }
    };
    

Log in to reply
 

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