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.



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? 

Credits:Special thanks to @pbrother for adding this problem and creating all test cases.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution:

	def combinationSum4(self, nums, target):
		cache = {}

		def f(val):
			if val == target:
				return 1
			total = 0
			remain = target - val
			for num in nums:
				if num <= remain:
					k = val + num
					if k in cache:
						total += cache[k]
					else:
						cache[k] = f(val + num)
						total += cache[k]
			return total
		return f(0)


class Solution:

	def combinationSum4(self, nums, target):
		record = {0: 1}

		def helper(target):
			if target in record:
				return record[target]
			res = 0
			for x in nums:
				if target >= x:
					res += helper(target - x)
			record[target] = res
			return res
		return helper(target)


class Solution(object):

	def combinationSum4(self, nums, target):
		dp = [0] + [-1] * target

		def calc(target):
			if target == 0:
				return 1
			if dp[target] >= 0:
				return dp[target]
			count = 0
			for n in nums:
				if target - n >= 0:
					tmp = calc(target - n)
					if tmp >= 0:
						count += tmp
			dp[target] = count
			return count
		ans = calc(target)
		print(ans)
		print(dp)
		return ans


class Solution:

	def combinationSum4_1(self, nums, target):
		res = 0
		if target == 0:
			return 1
		for i in range(len(nums)):
			if target >= nums[i]:
				res += self.combinationSum4(nums, target - nums[i])
		return res

	def combinationSum4_2(self, nums, target):
		dp = [-1] * (target + 1)
		dp[0] = 1
		return self.helper(dp, nums, target)

	def helper(self, dp, nums, target):
		if dp[target] != -1:
			return dp[target]
		res = 0
		for i in range(len(nums)):
			if target >= nums[i]:
				res += self.helper(dp, nums, target - nums[i])
		dp[target] = res
		return res

	def combinationSum4(self, nums, target):
		dp = [0] * (target + 1)
		dp[0] = 1
		for i in range(target + 1):
			for num in sorted(nums):
				if i < num:
					break
				dp[i] += dp[i - num]
		return dp[-1]


class Solution:

	def combinationSum4(self, nums, target):
		dp = [0 for x in range(target + 1)]
		dp[0] = 1
		for x in range(1, target + 1):
			for elem in nums:
				if x >= elem:
					dp[x] += dp[x - elem]
		return dp[-1]


class Solution:

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


class Solution:

	def combinationSum4_1(self, nums, target):
		res = 0
		if target == 0:
			return 1
		for i in range(len(nums)):
			if target >= nums[i]:
				res += self.combinationSum4(nums, target - nums[i])
		return res

	def combinationSum4_2(self, nums, target):
		dp = [-1] * (target + 1)
		dp[0] = 1
		return self.helper(dp, nums, target)

	def helper(self, dp, nums, target):
		if dp[target] != -1:
			return dp[target]
		res = 0
		for i in range(len(nums)):
			if target >= nums[i]:
				res += self.helper(dp, nums, target - nums[i])
		dp[target] = res
		return res

	def combinationSum4(self, nums, target):
		dp = [0] * (target + 1)
		dp[0] = 1
		for i in range(target + 1):
			for j in range(len(nums)):
				if i - nums[j] >= 0:
					dp[i] += dp[i - nums[j]]
		return dp[-1]


class Solution:

	def combinationSum4(self, nums, target):

		def dfs(nums, target, memo):
			if target in memo:
				return memo[target]
			if target < 0:
				return
			if target == 0:
				memo[target] = 1
				return
			memo[target] = 0
			for num in nums:
				dfs(nums, target - num, memo)
				if target - num >= 0:
					memo[target] += memo[target - num]
		dfs.count = 0
		nums.sort()
		memo = {}
		dfs(nums, target, memo)
		return memo[target]


class Solution:

	def combinationSum4(self, nums, target):
		self.dp = [-1] * (target + 1)
		self.dp[0] = 1
		return self.cSUtil(nums, target)

	def cSUtil(self, nums, target):
		if target < 0:
			return 0
		if self.dp[target] != -1:
			return self.dp[target]
		res = 0
		for num in nums:
			target -= num
			res += self.cSUtil(nums, target)
			target += num
		self.dp[target] = res
		return res


class Solution:

	def combinationSum4(self, nums, target):
		return self.use_dp(nums, target)

	def use_dfs(self, nums, target):
		self.result = 0
		nums.sort()
		self.dfs(nums, target)
		return self.result

	def dfs(self, nums, target):
		if target == 0:
			self.result += 1
			return
		for num in nums:
			if num > target:
				break
			self.dfs(nums, target - num)

	def use_recursion_dp(self, nums, target):
		dp = [-1] * (target + 1)
		dp[0] = 1
		nums.sort()
		return self.dp_dfs(nums, target, dp)

	def dp_dfs(self, nums, target, dp):
		if dp[target] != -1:
			return dp[target]
		result = 0
		for num in nums:
			if num > target:
				break
			result += self.dp_dfs(nums, target - num, dp)
		dp[target] = result
		return result

	def use_dp(self, nums, target):
		dp = [0] * (target + 1)
		dp[0] = 1
		for item in range(1, len(dp)):
			for num in nums:
				if item - num >= 0:
					dp[item] += dp[item - num]
		return dp[target]


class Solution:

	def combinationSum4(self, nums, target):
		if not nums:
			return 0
		n_nums = len(nums)
		combinations = [[0] * (n_nums + 1) for i in range(target + max(nums) + 3)]
		for i in range(1, target + 1):
			cur_sum = 0
			for j in range(n_nums):
				if i == nums[j]:
					combinations[i][j] = 1
				else:
					combinations[i][j] = combinations[i - nums[j]][n_nums]
				cur_sum += combinations[i][j]
			combinations[i][n_nums] = cur_sum
		return combinations[target][n_nums]


class Solution:
	count = 0

	def combinationSum4(self, nums, target):
		comb = [0] * (target + 1)
		comb[0] = 1
		for i in range(1, len(comb)):
			for j in range(0, len(nums)):
				if i - nums[j] >= 0:
					comb[i] += comb[i - nums[j]]
		return comb[target]