@@ -0,0 +1,1965 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0Aimport java.util.Arrays;%0A%0A/**%0A * Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add%0A * up to a positive integer target.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * nums = %5B1, 2, 3%5D%0A * target = 4%0A * %3Cp%3E%0A * The possible combination ways are:%0A * (1, 1, 1, 1)%0A * (1, 1, 2)%0A * (1, 2, 1)%0A * (1, 3)%0A * (2, 1, 1)%0A * (2, 2)%0A * (3, 1)%0A * %3Cp%3E%0A * Note that different sequences are counted as different combinations.%0A * %3Cp%3E%0A * Therefore the output is 7.%0A * Follow up:%0A * What if negative numbers are allowed in the given array?%0A * How does it change the problem?%0A * What limitation we need to add to the question to allow negative numbers?%0A * %3Cp%3E%0A * Tags: Dynamic Programming%0A * Similar Problems: (M) Combination Sum%0A */%0Apublic class CombinationSum4 %7B%0A%0A    private CombinationSum4 c;%0A%0Aprivate int%5B%5D dp;%0A%0A/**%0A *%0A * @param nums%0A * @param target%0A * @return%0A */%0Apublic int combinationSum4(int%5B%5D nums, int target) %7B%0A    dp = new int%5Btarget + 1%5D;%0A    Arrays.fill(dp, -1);%0A    dp%5B0%5D = 1;%0A    return helper(nums, target);%0A%7D%0A%0Aprivate int helper(int%5B%5D nums, int target) %7B%0A    if (target == 0) %7B%0A        return 1;%0A    %7D%0A    if (dp%5Btarget%5D != -1) %7B%0A        return dp%5Btarget%5D;%0A    %7D%0A    int res = 0;%0A    for (int i = 0; i %3C nums.length; i++) %7B%0A        if (target %3E= nums%5Bi%5D) %7B%0A            res += helper(nums, target - nums%5Bi%5D);%0A        %7D%0A    %7D%0A    dp%5Btarget%5D = res;%0A    return res;%0A%7D%0A%0A    @Before%0A    public void setUp() %7B%0A        c = new CombinationSum4();%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        int%5B%5D nums = %7B1, 2, 3%7D;%0A        int target = 4;%0A        Assert.assertEquals(7, c.combinationSum4(nums, target));%0A        target = 6;%0A        Assert.assertEquals(24, c.combinationSum4(nums, target));%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        c = null;%0A    %7D%0A%0A%7D%0A

add Combination Sum 4