C++ DP solution


  • 0
    G
        int countComb(vector<int>& nums, int target, int idx, vector<vector<int>>& table) {
            int ret = -1;
            if (table[idx][target] == -1) {
                if (target == 0) ret = 1;
                else if (idx == nums.size() || nums[idx] > target) ret = 0;
                else ret = countComb(nums, target - nums[idx], 0, table) + countComb(nums, target, idx + 1, table);
                table[idx][target] = ret;
            }
            return table[idx][target];
        }
        int combinationSum4(vector<int>& nums, int target) {
            vector<vector<int>> table(nums.size() + 1, vector<int>(target + 1, -1));
            sort(nums.begin(), nums.end());
            return countComb(nums, target, 0 /* index */, table);
        }
    

Log in to reply
 

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