LaiCode : Combination of coins

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