Leetcode 377. Combination Sum IV

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.

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.

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?

Thinking:

For problem of return the total number or max/min value. We may think about dynamic programming.

Complexity:

The time complexity is O(nk).

Step:

check whether input is valid
decide which DP we should use and what is the states equations
Initial the states
Dynamic programming

Code:

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

Conclusion:

When ask about the detailed solution we may use backtracking, when only ask about the number or the value of the solution, we may use dp.

Leetcode 377. Combination Sum IV