LeetCode: Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/, description of the problem:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Definitely a brute-force approach is exponential and won't work for large target numbers. Since the problem statement is asking only for the number of combinations (not actually the combinations themselves), then Dynamic Programming (DP) comes to mind as a plausible tool.
The DP code to solve this problem is very short, but the key is to grasp the idea behind it, which is usually not that straightforward. Here is the idea: instead of solving the problem for the "target" number, let's try to solve it for all the numbers from 1 to target. How can we solve the problem for the number 1? Clearly the first point is that to solve for "1" you can't allow any number in "nums" to be greater than "1", that seems logical. But the key insight comes now: to solve the problem for "1", let's go thru all the numbers up to "1" (which is only "1" in this case) and try to add that number ("1") to the solution. Adding that number to the solution means that we're looking for previous solutions "S" that add up to "1" (the target) - "1" (the current element in nums).
Basically keep an array "sums" of solutions for all the numbers from 1 to target. For each of the elements in the array construct the solution based on previous ones. The final solution will be stored on sums[target].
The explanation is very confusing, I completely agree, but that's because it takes me in general a long time to grasp DP, something that I keep pushing myself in order to master it in the same way that I can solve problems related to DFS/BFS. Key is to keep on practicing. Time complexity: O(nlogn + target*n). Cheers, Marcelo.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace LeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            Solution sol = new Solution();
            int[] nums = {1, 2, 3};
            int target = 4;

            Console.WriteLine(sol.CombinationSum4(nums, target));
        }
    }
    public class Solution
    {
        public int CombinationSum4(int[] nums, int target)
        {
            int[] sums = new int[target + 1];

            Array.Sort(nums);

            sums[0] = 1;
            for (int i = 1; i <= target; i++)
                for (int j = 0; j < nums.Length; j++)
                    if (i >= nums[j]) sums[i] += sums[i - nums[j]];
                    else break;

            return sums[target];
        }
    }
}