Отличные пути
Ссылка: 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 */