C++ Solution using DP with O(max(nlgn, target*n))


  • 0
    Y

    Here dp[i] means that the number of combinations adding up to number i. So the final answer is dp[target].

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

Log in to reply
 

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