leetcode-377-组合总和IV

//当输入测试用例为 [3,33,333], 10000时，编译器大整数相加溢出，使用unsigned long long来存储

class Solution {

public:

    int gcd(int a, int b) {

        return b == 0 ? a : gcd(b, a % b);

    }

    int combinationSum4(vector<int>& nums, int target) {

        if (nums.size() == 0) return 0;

        vector<unsigned long long> dp(target+1,0);

        sort(nums.begin(), nums.end());

        int base = nums[0];

        if (target < base) return 0;

        dp[0] = 1;

        for (int i=base; i<target+1; i++){

            for (auto n:nums){

                if (n > i) break;

                dp[i] += dp[i-n];

            }

        }

        return dp.back();

    }

};