动态规划：排列与组合的区别
1.组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
题目分析：
看完题目要求，再看示例 1，你可能会想到这是一个完全背包问题。但是如果这道题真的问的是组合的话，前面出现 (1, 1, 2) 后面就不会出现 (1, 2, 1) 和 (2, 1, 1) 这样的情况。题目把这三种情况当成了不同的情况，也就是顺序不一样它们也是属于不同组合。
但是实际上 排列 和 组合 是不一样的，排列是有序的，组合是无序的。
如果这道题问的是组合，也就不考虑选出来数的顺序，那 (1, 1, 2)、(1, 2, 1)、(2, 1, 1) 就只属于一种情况，不管它是什么组合。
而排列是有序的，要保证选出来数字的先后顺序。
所以这道题应该叫做排列总和才对。
算法原理：
实质上背包问题都是解决这一类问题：有限制条件下的'组合'问题
从状态表示 dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j，所有的选法中，最大的价值来看，我们的状态表示从来没有规定过挑选的顺序。而只是在两个限定条件下，所有的选法中，要最大价值即可。
因此我们挑选出来的所有选法都是没有顺序的。所以背包问题实质上解决的'组合'问题。
当用背包问题去解决方案数的时候，其实求的是'组合'数。而这道题问的是组合数实际上求的是排列数。所以这道题不能用背包问题解决。
我们就用常规的状态表示来分析这道题。
- 状态表示
这里我们学一种新的状态表示法。之前做的大多数问题都是用的是线性 dp 或者区间 dp 来解决，所以之前的经验都是以某个位置为结尾，巴拉巴拉。或者以某个位置为起点，巴拉巴拉。或者选取一段区间巴拉巴拉。
但是这道题既不像线性 dp 也不像区间 dp，我们可以这样来：
根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示。
接下来以一个例子来说什么是重复子问题。比如这道题，给我们一堆数假设是 [a、b、c、d]，然后看看凑成 target，一共有多少种排列数。如果要看排列数一定要看看每个位置怎么选，因为每个位置选数要考虑先后顺序。假设凑成 target 需要四个位置，第一个位置可以选 [a、b、c、d]、第二个位置也可以选 [a、b、c、d]…，如果第一个位置放了 a，那接下来就看剩下的位置凑出来 target - a。重复的问题是本来想要的是整个区间凑成 target，然后固定一个数之后发现整个区间凑成 target - a 就可以了。也就是说我们的相同问题是看凑成一个数有多少种方法。本来想看凑成 target 有多少种方法，接下来就是去看 target - a 有多少种方法。这就是重复子问题。
接下来将重复子问题，抽象出来一个状态表示。想看一个数有多少种方法，我们搞一个一维数组。
dp[i] 表示：凑成总和为 i，一共有多少种排列数。
本来想看凑成 target 有多少种方法，接下来发现固定完一个数就是去看 target - a 有多少种方法。这就是根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示。
- 状态转移方程
如果能用上面那种方式定义状态表示，其实状态转移方程就和上面一模一样。 我们用一条线长度表示 target。我们细分用最后一个位置划分情况。
假设最后一个位置的数是 nums[j]（0 <= j <= n.size()）表示数组里任意一个数都可以放到最后一个位置。
如果最后一个位置放的是 nums[j]，整体想凑成总和 i，那仅需看看凑成 i - nums[j] 有多少种方法。
