377. Combination Sum IV

题目要求

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

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

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

有一个不包含重复值的正整数数组nums,问从数组中选择几个数,其和为target,这样的数的组合有几种?

思路一:自顶向下的dp

这题本质上需要注意一点,就是我如果需要组成target,那么一定是由nums中的一个值和另一个值的排列组合结果构成的。比如com[4] = com[4-1] + com[4-2] + com[4-1]。通过这一点,我们构成一个递归表达式,但是因为单纯的递归表达式没有计算中间结果,所以会造成大量重复的计算影响效率,所以这里采用dp的思路额外的用数组来记录已经计算过的com结果。比如com[3] = com[2] + com[1], com[2] = com[1],如果没有dp,则需要重复计算com[1]的结果。

    public int combinationSum4(int[] nums, int target) {
            if (nums == null || nums.length < 1) {
                return 0;
            }
            int[] dp = new int[target + 1];
            Arrays.fill(dp, -1);
            dp[0] = 1;
            return helper(nums, target, dp);
        }
        
        private int helper(int[] nums, int target, int[] dp) {
            if (dp[target] != -1) {
                return dp[target];
            }
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                if (target >= nums[i]) {
                    res += helper(nums, target - nums[i], dp);
                }
            }
            dp[target] = res;
            return res;
        }

思路二:自底向上dp

    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] combinationCount = new int[target+1];
        
        combinationCount[0] = 1;
        
        for(int i = 1 ; i<=target ; i++) {
            for(int j = 0 ; j<nums.length && nums[j] <= i ; j++) {
                combinationCount[i] += combinationCount[i - nums[j]];
            }
        }
        return combinationCount[target];
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode398. Random Pick Index

    设计一个数据结构,使得从该数据结构中查询一个数字时,能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。

    眯眯眼的猫头鹰
  • leetcode480. Sliding Window Median

    Median is the middle value in an ordered integer list. If the size of the list i...

    眯眯眼的猫头鹰
  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • LintCode 563. 背包问题 V(DP)

    给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。

    Michael阿明
  • Leetcode 34 Search for a Range

    Given a sorted array of integers, find the starting and ending position of a gi...

    triplebee
  • 多组学整合药物预测如何发6分SCI的?

    •IC50 (half maximal inhibitory concentration)最大半抑制浓度,可以用来衡量药物诱导凋亡的能力,即诱导能力越强,该数值...

    百味科研芝士
  • 苹果的设计中是如何应用 “施奈德曼 黄金准则”的?

    苹果公司,作为一家科技巨头,其大量的设计思想非常恰当的反映了Shneiderman(施奈德曼)的8条黄金准则是如何创建出优秀成功的产品的。他们也一直骄傲于自己出...

    前朝楚水
  • 全国首张地铁、出租车区块链电子发票在深圳开出

    3月18日,全国首张轨道交通区块链电子发票在深圳地铁福田站开出,正式宣告深圳市地铁乘车码上线区块链电子发票功能。即日起,用户使用腾讯旗下智慧交通出行产品乘车码搭...

    腾讯TrustSQL
  • LeetCode 713. 乘积小于K的子数组(滑动窗口)

    Michael阿明
  • 【图像分割 】开源 | CVPR2020 | 深度学习框架 | Morpheus天文图像数据像素级分析的深层学习框架

    我们提出了一种新的学习框架Morpheus,用于生成天文学像素级的形态学分类。Morpheus框架以深度学习为基础,通过计算机视觉领域的语义分割算法,逐像素地执...

    CNNer

扫码关注云+社区

领取腾讯云代金券