顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 377] Combination Sum IV [Java] [Runtime : 6MS]
09/02
1. Description
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.
2. Runtime Distribution
3. Submission Details
4. 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.
5. Code
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int num : nums) {
if (i + num <= target) {
dp[i + num] += dp[i];
}
}
}
return dp[target];
}6.Test
public class LeetCode0377 {
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int num : nums) {
if (i + num <= target) {
dp[i + num] += dp[i];
}
}
}
return dp[target];
}
public static void main(String[] args) {
LeetCode0377 leetcode = new LeetCode0377();
int[] nums = { 1, 2, 3 };
System.out.println(leetcode.combinationSum4(nums, 4));
}
}
