Why care about line numbers, my DP c++ solution


  • 0
    B
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target)
        {
            if (nums.size() == 0)
                return 0;
            int rows = nums.size();
            int cols = target + 1; // keep the first column not used
            vector<vector<int>> table(rows, vector<int>(cols, 0));
            sort(nums.begin(), nums.end());
            for (int r = 0; r < rows; r++)
            {
                int token = nums[r];
                for (int val = 1; val <= cols; val++)
                {
                    if (r == 0 && val % token != 0)
                        table[r][val] = 0;
                    else if (r == 0 && val % token == 0)
                        table[r][val] = 1;
                    else if (r > 0 && val < token)
                        table[r][val] = table[r-1][val];
                    else if (r > 0 && val == token)
                        table[r][val] = table[r-1][val] + 1;
                    else if (r > 0 && val > token)
                    {
                        for (int ri = 0; ri <= r; ri ++)
                        {
                            table[r][val] += table[r][val - nums[ri]];
                        }
                    }
                }
            }
            return table[rows-1][cols-1];
        }
    };
    

Log in to reply
 

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