GuilinDev

Lc0377

05 August 2008

377 Combination Sum IV

Given an array of distinct integers 

1

nums
and a target integer 
1

target
, return the number of possible combinations that add up to 
1

target
.

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.

Example 2:

1
2

Input: nums = [9], target = 3
Output: 0

Constraints:

  • 1

    1 <= nums.length <= 200

  • 1

    1 <= nums[i] <= 1000
  • All the elements of 
    1

    nums
    are unique.
  • 1

    1 <= target <= 1000

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， 和找硬币是一个系列的，不过找硬币1是找的最优解，找硬币2找的是解的组合总数，这个题求的是找排列的个数。

排列的个数不需要考虑顺序

因此dp[i]表示钱数为i的时候排列的个数

怎么求dp[i]?

不需要考虑顺序，所以dp[i]为求每个硬币对构成金钱为i时候的贡献，因此不需要硬币放置的顺序， 因此dp[i] =所有dp[i - 每一个硬币]的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public static int combinationSum4(int[] nums, int target) {
        int len = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < len; j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}
This site is open source. Improve this page.