class Solution(object):
def helper(self, coins, remaining, chosen, res, curr_idx):
"""
@coins: a list of coins
@remaining: how much we have to got
@chosen: a vector of coins we have chosen
@res: a vector to store results
@last_choice_idx: the index for this round
"""
if (remaining == 0):
res.append(chosen.copy())
return
elif (curr_idx > len(coins)-1):
return
curr = coins[curr_idx]
max_num = math.floor(remaining/curr) # the maximum number we can choose for this kind of coins
for i in range(max_num+1):
# choose
chosen[curr_idx] = i # record how many coins of this kind do we choose
remaining -= curr * i
# explore
self.helper(coins, remaining, chosen, res, curr_idx+1)
# unchoose
chosen[curr_idx] = 0
remaining += curr * i
def combinations(self, target, coins):
"""
input: int target, int[] coins
return: int[][]
"""
# write your solution here
res = []
chosen = [0] * len(coins)
self.helper(coins, target, chosen, res, 0)
return res
思路2: 每一层的物理意义是这一层选几个。
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.