phntom · January 2, 2017 18:01
diff --git a/coin_sum.py b/coin_sum.py
 ### NaiveMultiCoinSum ###
 # this is O(2^n) runtime and O(n) space
 def coin_sum(coins, target_sum):
  # the number of coins combinations that sum to target
  seen_ordered = set()
  seen_unordered = set()
  coin_sum_aux(coins, target_sum, [], seen_ordered, seen_unordered)
  return len(seen_ordered), len(seen_unordered)

 def coin_sum_aux(coins, remainder, current_pick, seen_o, seen_u):
  if remainder == 0:
    seen_o.add(tuple(current_pick))
    seen_u.add(tuple(sorted(current_pick)))
    return
  for x in coins:
    if x > remainder:
      continue
    else:
      coin_sum_aux(coins, remainder - x, current_pick + [x], seen_o, seen_u)
        
        
 ### CoinPairSum ###
 def coin_pair_sum(coins, target_sum):
  # the number of coins that can be summed in pairs to target
  coins_set = set(coins)
  count = 0
  for coin in coins:
    if coin <= target_sum and target_sum - coin in coins_set:
      count += 1
  return count

 ### DP ###
 from collections import defaultdict
 from math import ceil
 # runtime - O(target^2 * coins^2)
 def coin_sum(coins, target):
  m = min(coins)
  assert m > 0
  max_number_of_coins = int(ceil(target / m))

  next_remainder_to_coins_set = defaultdict(set)
  for coin in coins:
    next_remainder_to_coins_set[coin] = { (coin,) }
  
  count = 0
  for number_of_coins in range(2, max_number_of_coins + 1):  # O(target)
    # range(start, end) returns [start, start+1, ... end-1]
    remainder_to_coins_set = next_remainder_to_coins_set
    count += len(remainder_to_coins_set[target])

    next_remainder_to_coins_set = defaultdict(set)
    for coin_set_sum, coin_set in remainder_to_coins_set.items():  # O(target)
      for coin in coins:  # O(coins)
        if coin_set_sum + coin > target:
          continue
        for x in coin_set:  # O()
          entry = x + (coin,)
          next_remainder_to_coins_set[sum(entry)].add(entry)

  count += len(next_remainder_to_coins_set[target])
  return count

 print coin_sum([1, 2, 5, 10], 10)  # (129, 11)
	### NaiveMultiCoinSum ###
	# this is O(2^n) runtime and O(n) space
	def coin_sum(coins, target_sum):
	# the number of coins combinations that sum to target
	seen_ordered = set()
	seen_unordered = set()
	coin_sum_aux(coins, target_sum, [], seen_ordered, seen_unordered)
	return len(seen_ordered), len(seen_unordered)

	def coin_sum_aux(coins, remainder, current_pick, seen_o, seen_u):
	if remainder == 0:
	seen_o.add(tuple(current_pick))
	seen_u.add(tuple(sorted(current_pick)))
	return
	for x in coins:
	if x > remainder:
	continue
	else:
	coin_sum_aux(coins, remainder - x, current_pick + [x], seen_o, seen_u)


	### CoinPairSum ###
	def coin_pair_sum(coins, target_sum):
	# the number of coins that can be summed in pairs to target
	coins_set = set(coins)
	count = 0
	for coin in coins:
	if coin <= target_sum and target_sum - coin in coins_set:
	count += 1
	return count

	### DP ###
	from collections import defaultdict
	from math import ceil
	# runtime - O(target^2 * coins^2)
	def coin_sum(coins, target):
	m = min(coins)
	assert m > 0
	max_number_of_coins = int(ceil(target / m))

	next_remainder_to_coins_set = defaultdict(set)
	for coin in coins:
	next_remainder_to_coins_set[coin] = { (coin,) }

	count = 0
	for number_of_coins in range(2, max_number_of_coins + 1): # O(target)
	# range(start, end) returns [start, start+1, ... end-1]
	remainder_to_coins_set = next_remainder_to_coins_set
	count += len(remainder_to_coins_set[target])

	next_remainder_to_coins_set = defaultdict(set)
	for coin_set_sum, coin_set in remainder_to_coins_set.items(): # O(target)
	for coin in coins: # O(coins)
	if coin_set_sum + coin > target:
	continue
	for x in coin_set: # O()
	entry = x + (coin,)
	next_remainder_to_coins_set[sum(entry)].add(entry)

	count += len(next_remainder_to_coins_set[target])
	return count

	print coin_sum([1, 2, 5, 10], 10) # (129, 11)
No results found