子集合问题，这两个算法有什么区别？

Question

普通的子集和问题:给定一个已经排序且无重复的数组，以及一个目标值，输出子集合为目标值的个数，例如：

nums = [1, 2, 3]
target = 4

满足条件的子集为：

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

则输出结果为：7

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

上面的代码是正确的算法，这是 LeetCode 上最近的一道题，跟找零钱算法（给定一个数组，即币种面值的集合，返回一个目标值可以有多少种零钱组合）很类似，对于找零钱算法，上面的(1, 1, 2)，(1, 2, 1)，(2, 1, 1) 只能计算一次，(1, 3)、(3, 1) 也只能计算一次，结果为 4

找零钱算法是这样子的：

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = num; i <= target; ++i) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }

找零钱算法就是对子集合算法的结果去重得到的，代码上的差别仅仅是内外两重循环的顺序变了，这个我就不太理解，为什么循环顺序变了，会导致一个结果含重复序列，另一个不含？换言之，找零钱算法相比较子集合算法，是如何避免重复的呢？

Answer 1

谢邀，非常好的问题！

DP 从来都是很抽象的，希望我能说清楚。

仔细品味两种方法，你会发现：第二种被非常隐晦地人为地加上了一种“序”。

假设同时有个三维数组 result[target][i][j]，用于储存所有可能的结果集：result[target][i] 为一个数组，存储的是 和为 target 的第 i 种可能子集 。处理 dp[i] 时，假想同时有个 将 result[i - num] 下所有序列拷贝到 result[i] 下，同时往所有 result[i][index] 的最后面添加一个 num 的操作。这样结果集就会同步生成。

在第一种算法中，计算 某个 result[i] 时，我们需要用到 result[i - num]，而由于循环 num: nums 在内层，result[i - num] 中有可能出现 在 nums 中 比 num 要靠后的项。

而在第二种算法中，由于循环 num: nums 在外层，使用 result[i - num] 时，其储存的结果集包含的元素只可能来自于 nums 中排在 num 前面的元素（因为后面的还没遍历到）。换句话说：如果将 result 打印出来，那么每个结果集的元素排列必定是按照原先在 nums 中的顺序。既然有了顺序，那么自然不会计算重复项了。