Leetcode-377: Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

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:

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

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

Thoughts

Core extraction: Unsorted & Distinct & Results disorder

Results disorder

It’s vital to aware that the result can actually be unordered.For example, (1, 1, 2) & (1, 2, 1) are actually two different valid paths, which I overlooked in the beginning.

• 🤔 Solving with Map? Segment Tree? Binary Tree?
• 🤔 Reversal decrease -> Recursion -> ⚠️ Potential OverTime Risk
• 👍 Dynamic Programming

Solution

Recursion

As to number target, we can divide it into multiple steps, in each step, we will subtract the number with anyone of the given numbers, and then do next step, until the total subtraction reaches zero. Then we get one complete path. So if we record all the valid path, and add it up, finally we will get the answer.

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        return recursion(nums, target, map);
    }

    public int recursion(int[]nums, int num, Map<Integer, Integer> map) {
        if (map.get(num) != null) {
            return map.get(num);
        }
        if (num == 0) {
            return 1;
        }
        if (num < 0) {
            return 0;
        }        
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (map.get(num - nums[i]) != null) {
                count += map.get(num - nums[i]);
            } else {
                int curCount = recursion(nums, num - nums[i], map);
                if(curCount > 0) {
                    count += curCount;
                    map.put(num - nums[i], curCount);
                }
            }
        }
        return count;
    }
}

With Hash Optimizaiton

Logic Inference

In the solution above, we have done many meaningless and redundant calculation -- We have repeatedly calculated path count for same numbers. And due to the recursion method, it would take actually quite extra times and stack use. So we need to eliminate useless calculating.

For one specific number, if we already know the number of the path, then we can directly return the answer. So we should store the path number for one specific number.

Result

❌ Not Qualified -- Overtime Like most likely recursion solution, it may be convenient to think and implement. But its time-complexity and stack-use are not pretty as simplicity of its implementation.

So if you just quickly think of recursion in the first time, try not to use it, because in great possibility it may not be the perfect answer, even the viable answer for qualified time-complexity.

Dynamic Programming

Viability: Valid paths count of target N + 1 can be calculated by history recording by target range from 1 to N, with just one step.

$$\{\begin{array}{l}P(0)=1\\ P(N)=\sum _{i=0}^{nums.length-1}P(N-nums[i])(N-nums[i]\ge 0)\end{array}$$

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
              	// avoid index out of bound error
                if (i - nums[j] >= 0) {
                    count += dp[i - nums[j]];
                }
            }
            dp[i] = count;
        }
        return dp[target];
    }
}

Time-Complexity $O(nums.length\ast N)$

Result-1