leetcode Combination Sum IV

leetcode 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:

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?

题目地址:leetcode Combination Sum IV

题意:给定一个元素互不相同且均为正数的数组,让你用该数组中的数组合成target(可以重复使用),问有多少种。

思路:DP可以有两种

  • dp[i] += dp[i-num]
  • dp[i+num] += dp[i]

其实和 322 Coin Change 那题差不多。。。

 

第一种DP

C++

Java

Python

 

第二种DP
C++

Java

Python

 

 

 

本题是leetcode 377 Combination Sum IV题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Combination Sum IV
本文地址:https://www.hrwhisper.me/leetcode-combination-sum-iv/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

8 thoughts on “leetcode Combination Sum IV

  1. 觉得楼主的DP算法好精简,赞,这个解的想法是从一个状态(现有和)到另外一个状态的所有可能路径(nums)内容相加,对吗?

    • 对。
      dp[i+num] += dp[i] 可以这么说,当前状态再加一个数可以变成啥。
      而dp[i] += dp[i-num] 也是类似的,当前状态可以由那些状态构成。

    • 有负数的情况可能存在无限符合要求的解。(比如你想想有个-1的,我正数随便加,然后再减回去)
      所以必须要有限制条件,限制条件有很多啊 比如要求解的长度为L,或者不超过L,或者每个数只能使用X次等等

Leave a Reply

Your email address will not be published. Required fields are marked *