Отличные пути

Ссылка: https://leetcode.com/problems/combination-sum-iv/description/?envType=list&envId=55ajm50i

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<unsigned long> dp(target+1, 0);
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < n; j++) {
                if (i == nums[j]) dp[i]++;
                else if (i > nums[j]) dp[i] += dp[i-nums[j]];
            }
        }
        return dp[target];
    }
};
/**
Distinct integer nums
target integer target
possible combinations that up to target

nums = [1, 2, 3], target = 4
check val <= 4
4 - val[x] forall x in 0 to n-1
4-1 = 3, 3-1 = 2(prev) = 2 - 1 = 1(prev) = 1
2 - 2 = 0
4-2 = 2 
4-3 = 1 -> 1

4 - 1 = 3
4 - 2 = 2
4 - 3 = 1
3 - 1 = 2
3 - 2 = 1
3 - 3 = 0 
2 - 1 = 1
2 - 2 = 0
1 - 1 = 0
1 val = 1 way reach
2 val = 2 way reach
3 val = 4 way reach
4 val = 7 way reach

32 bit integer - unsigned long
*/