Share my C++ solution using DP, easy to understand


  • 0
    V
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            int ret;
            int n = nums.size();
            vector<int> cnt(target + 1, 0);
            cnt[0] = 1;
            
            sort(nums.begin(), nums.end());
            
            for (int sum = 1; sum <= target; sum++)
            {
                for (int i = 0; i < n; i++)
                {
                    if (nums[i] > sum)
                        break;
                    
                    cnt[sum] += cnt[sum- nums[i]];
                }
            }
            
            return cnt[target];
        }
    
    };
    

Log in to reply
 

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