377. Combination Sum IV - cocoder39/coco39_LC GitHub Wiki

377. Combination Sum IV

This should be called permutation sum since [1,1,2] and [1,2,1] are counted as different

518. Coin Change 2 is actually combination sum. Check the difference

Notes 2020:

Solution 1 - DP (preferred)

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * target
        nums.sort()
        
        for i in range(target + 1):
            if dp[i] > 0:
                for num in nums:
                    if i + num > target:
                        break
                    dp[i+num] += dp[i]
        return dp[target]

Time complexity: O(NLogN + NTarget)

Solution 2 - backtrack

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        return self.helper(nums, target)
        
    def helper(self, nums: List[int], target):
        if target == 0:
            return 1
        
        if not nums or target < nums[0]:
            return 0
        
        count = 0
        for i in range(len(nums)):
            count += self.helper(nums, target-nums[i])
        return count

Time complexity: O(C(N, K)) where K = target / min(nums)

====================================================================

return the number of solutions, use dp; return all solutions, use backtracking

time is O(n * max(log n, target))

int combinationSum4(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            if (dp[i] != 0) {
                for (auto num : nums) {
                    if (i + num > target)   break;
                    dp[i + num] += dp[i];
                }
            }
        }
        return dp[target];
    }

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

suppose given [-1, 1] and target is 1. If an element can be repeatedly used, we can generate unlimited solutions [1], [-1, 1, 1], [-1, 1, -1, 1, 1]...

Thus adding limitation that limiting the number of negative elements in final result, or the number of positive elements, or the total length of final result...
⚠️ **GitHub.com Fallback** ⚠️