LC 377. Combination Sum IV

发布时间：2020-12-14 05:15:19 所属栏目：大数据来源：网络整理

导读：? 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 = 4The possible combination ways are:(1,1,1)(1,2)(1,3)(2

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,2)
(1,3)
(2,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?

Credits:
Special thanks to?@pbrother?for adding this problem and creating all test cases.

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,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?

Credits:
Special thanks to?@pbrother?for adding this problem and creating all test cases.

Runtime:?2 ms,faster than?80.43%?of?Java?online submissions for?Combination Sum IV.

class Solution {
  public int combinationSum4(int[] nums,int target) {
    int[] dp = new int[target+1];
    dp[0] = 1;
    for(int i=0; i<dp.length; i++){
      for(int j=0; j<nums.length; j++){
        if(i >= nums[j]){
          dp[i] += dp[i - nums[j]];
        }
      }
    }
    return dp[target];
  }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!