正文

Leetcode: Combination Sum IV && Summary: The Key to Solve DP

IP云V管理员/2022-12-01/6 阅读

12/01

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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?

DP 解法： the key to solve DP problem is to think about how to create overlap, how to re-solve subproblems（怎么制造复用）

Bottom up dp:

 public class Solution {

     public int combinationSum4(int[] nums, int target) {

         if (nums==null || nums.length==0) return 0;

         Arrays.sort(nums);

         int[] dp = new int[target+1];

         dp[0] = 1;

         for (int i=1; i<=target; i++) {

             for (int j=0; j<nums.length && nums[j]<=i; j++) {

                 dp[i] += dp[i-nums[j]];

             }

         }

         return dp[target];

     }

 }

Better Solution(Bottom-up)不sort也成：

 public int combinationSum4(int[] nums, int target) {

     int[] comb = new int[target + 1];

     comb[0] = 1;

     for (int i = 1; i < comb.length; i++) {

         for (int j = 0; j < nums.length; j++) {

             if (i - nums[j] >= 0) {

                 comb[i] += comb[i - nums[j]];

             }

         }

     }

     return comb[target];

 }

Follow up:

I think if there are negative numbers in the array, we must add a requirement that each number is only used one time, or either positive number or negative number should be used only one time, otherwise there would be infinite possible combinations.
For example, we are given:
{1, -1}, target = 1 ,
it's obvious to see as long as we choose n 1s and (n-1) -1s , it always sums up to 1, n can be any value >= 1.

Leetcode: Combination Sum IV && Summary: The Key to Solve DP的更多相关文章

[LeetCode] Combination Sum IV 组合之和之四
Given an integer array with all positive numbers and no duplicates, find the number of possible comb ...

[LeetCode] Combination Sum III 组合之和之三
Find all possible combinations of k numbers that add up to a number n, given that only numbers from ...

[LeetCode] Combination Sum 组合之和
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C wher ...

LeetCode Combination Sum III
原题链接在这里:https://leetcode.com/problems/combination-sum-iii/ 题目: Find all possible combinations of k n ...

Combination Sum | & || & ||| & IV
Combination Sum | Given a set of candidate numbers (C) and a target number (T), find all unique comb ...

LC 377. Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible comb ...

[LeetCode] 377. Combination Sum IV 组合之和之四
Given an integer array with all positive numbers and no duplicates, find the number of possible comb ...

[LeetCode] 377. Combination Sum IV 组合之和 IV
Given an integer array with all positive numbers and no duplicates, find the number of possible comb ...

[LeetCode] Combination Sum II 组合之和之二
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in ...

随机推荐

Fingerprinting
https://wiki.mozilla.org/Fingerprinting Fingerprinting Contents 1 Overview 2 Data 2.1 Plugins 2.2 ...

7添加一个“X”到HTML：转到XHTML
XHTML中的X代表extensible,是以XML为基础的另一种说法.XML表示可扩展的标记语言. XML是一种可以用来开发新的标记语言的语言,而HTML只是一门标记语言. HTML转化为XHTML ...

php 通过exec 创建git分支失败
今天给我们自己的发布系统增加一个新建分支的功能,操作比较简单,但是使用php执行shell命令的时候总是无法push分支到远程,但是登陆服务器执行却是可以的新建分支命令如下 git fetch -- ...

cookie函数
function getcookie(){ var cookie={}; var all=document.cookie; if(all===""){ alert(2); retu ...

【nodejs】使用Node.js实现REST Client调用REST API
最近在产品中开发基于REST的API接口,结合自己最近对Node.js的研究,想基于它开发一个REST Client做测试之用. 通过初步研究,Node.js开发HTTP Client还是挺方便的. ...

IIS8中部署WCF服务出错：HTTP 错误 404.3 - Not Found
解决方法,以管理员身份进入命令行模式,运行: "%windir%\Microsoft.NET\Framework\v3.0\Windows Communication Foundation\ ...

导出证书Cer文件为Pem格式的步骤
(1)先导出Push Services的证书,比如我们命名为“magic_cert.p12”,注意导出时会让你输入密码. (2)再导出Push Services证书的密钥(Private Key),比 ...

解析const
const在函数前与函数后的区别一 const基础如果const关键字不涉及到指针,我们很好理解,下面是涉及到指针的情况: int b = 500; ...

Nodejs路由之间的数据传递
实例是模拟登录页面提交表单,然后根据信息判断是否登录成功 login.js var express =require('express'); var router =express.Router(); ...

Magento修改邮件模板内容
Magento 默认邮件模板都是带着官方的标志和一些官方的基本信息.为了建立品牌形象我们需要把邮件模板中的所有官方信息换成自己的信息.修改步骤如下: 1.找到Magento的邮件模板文件(这里以 e ...

相关阅读

目录[+]