【每日一题4.24】377. 组合总和 Ⅳ

时间:2021-6-12 作者:qvyue

题目

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
示例 2:

输入:nums = [9], target = 3
输出:0

提示:

1
1
nums 中的所有元素 互不相同
1

思路

简单dp:定义dp[i]:表示用所给元素组成i的方案数,其实你会发现这好像是个多重背包问题呀。

java代码

class Solution {
      public int combinationSum4(int[] nums, int target) {  
        Arrays.parallelSort(nums);
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。