组合总和Ⅳ

题目

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

代码

深度有限搜索超时

    int count;

    public int combinationSum4(int[] nums, int target) {
        count = 0;
        Arrays.sort(nums);
        dfs(nums, 0, target);
        return count;
    }

    private void dfs(int[] nums, int pos, int target) {
        if (target == 0) {
            count++;
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (target - nums[i] < 0) {
                break;
            }
            dfs(nums, i, target - nums[i]);
        }
    }

动态规划

    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 (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }