我目前正在尝试在 Python 中实现动态规划，但我不知道如何设置回溯部分以使其不重复排列。例如，输入将是 (6，...

我目前正在尝试在 Python 中实现动态规划，但我不知道如何设置回溯部分以使其不重复排列。例如，输入为 (6, [1,5])，预期输出应为 2，因为有 2 种可能的方式排列 1 和 5，使它们的总和等于 6。这些组合是 {1,1,1,1,1,1} 和 {1,5}，但我的程序当前的工作方式考虑了上面显示的组合和组合 {5,1}。这导致输出为 3，这不是我想要的。所以我的问题是“如何防止重复排列？”。我当前的代码如下所示。

    import collections as c

    class DynamicProgram(object):
        def __init__(self):
            self.fib_memo = {}
            # nested dictionary, collections.defaultdict works better than a regular nested dictionary
            self.coin_change_memo = c.defaultdict(dict)
            self.__dict__.update({x:k for x, k in locals().items() if x != 'self'})
        def coin_change(self, n, coin_array):
            # check cache
            if n in self.coin_change_memo:
                if len(coin_array) in self.coin_change_memo[n]:
            return [n][len(coin_array)]

            # base cases
            if n < 0: return 0
            elif n == 1 or n == 0: return 1

            result = 0
            i = 0

            # backtracking (the backbone of how this function works)
            while i <= n and i < len(coin_array):
                result += self.coin_change(n-coin_array[i], coin_array)
                i += 1

            # append to cache
            self.coin_change_memo[n][len(coin_array)] = result

            # return result
            return result