377. Combination Sum IV

题目描述和难度

• 题目描述：给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
• 题目难度：中等。
• 英文网址：377. Combination Sum IV 。
• 中文网址：377. Combination Sum IV 。

思路分析

求解关键：按照下图所示的规律找到递归关系式，体会我们在这道题的求解过程中是如何进行搜索的，我们不是胡乱搜索，而是按照顺序搜索：每次都减去一枚硬币的值，看减去了一枚硬币的剩余价值的组合个数有多少，和没有减去这枚硬币的价值的组合个数建立关系。

参考解答

参考解答1

public class Solution {

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        // 这一步很关键，想想为什么 dp[0] 是 1
        // 因为 0 表示空集，空集和它"前面"的元素凑成一种解法，所以是 1
        // 这一步要加深体会
        dp[0] = 1;
        for (int i = 1; i < target + 1; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] = dp[i] + dp[i - num];
                }
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3};
        int target = 4;
        int combinationSum4 = solution.combinationSum4(nums, target);
        System.out.println(combinationSum4);
    }
}