DP_Mock_Interview Question

DP_Mock_Interview_Question.py

'''
	football 
	each play can lead 2,3 or 7 points.
	
	if we are given some score of p find out 2,3 and 7 
	
	how many diff perm 
	
	p = 7
	
	perm count = 4 
	
	
	7
	
	2+3+2
	
	3+2+2
	
	2+2+3
	
	---------
	
	
	
			2                       3                  7
	 2      3       7        2      3    7            (7) 
   3   7   2   3           2   3    x    x
  (7)  x   (7) x          (7)  x 
  
	
'''  

def overall(nums, target):
	
	if len(nums) > 5:
		return 0

	hset = set()
	nums.sort()
	n = len(nums)
	count = 0

	def helper(num,remain,slate):

		nonlocal count

		if remain == 0:
			if not str(slate[:]) in hset:
				count += 1
			return
		elif remain < 0:
			return

		else:
			for num2 in nums:
				
				if str(slate[:]) in hset:
					continue

				slate.append(num2)
				helper(num2,remain - num2, slate)
				hset.add(str(slate[:]))
				slate.pop()

	for num in nums:
		helper(num,target,[])

	return count


points = [2,3,7]
target = 7

res = overall(points, target)
print("res : ", res)

'''
  T(N) = O(N.N!)
'''

def combinationSum(numbers, target):

	if target == 0:
		return 1  # base case

	count = 0

	for number in numbers:
		if number <= target:
			count += combinationSum(numbers, target - number)

	return count



points = [7,3,2]
target = 7

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

res = combinationSum(points, target)
print("res : ", res)