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
[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]
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]; }
[/restab]
[/restabs]
6.Test
[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]
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)); } }
[/restab]
[/restabs]
Comments | NOTHING