LeetCode 518. Coin Change 2

Problem

LeetCode 518. Coin Change 2

1. 题目简述

给出一组不重复的coins，以及目标金额amount，找出所有能够组成目标金额的硬币组合方式的数量。例如：

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

2. 算法思路

动态规划中最经典的背包问题之完全背包问题，可以参考着这篇labuladong大佬的blog来看：传送门

动态规划

经典问题之一的完全背包问题，指的是在不限制每种物品的情况下，一共有多少种可能的组合，使得背包装满。

回溯

那么为什么会想到回溯呢？没有为什么，因为回溯能做出来这种需要遍历所有可能的问题。就这么简单。

对于一个数组A和某个target值，我们希望找出target所有的组合可能，假设F(int[] A, int start, int target)为从数组A中以start为起点找出target的所有可能组合，思路如下。

1. 对A从小到大进行排序，取A[0]作为第一个数，那么我们当前的目标是F(A, 0, target - A[0])；将其结果和A[0]放在一起作为第一种解。
2. 然后取A[1]作为第一个数，然后我们目标是F(A, 1, target - A[1])。不从0开始是因为如果取了0，就会和第一步中的某种solution重复，故不取。
3. 终止条件为target == 0，最终结果添加一条；target < 0，回溯上去继续搞。