377. Combination Sum IV

Description

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

The answer is guaranteed to fit in a 32-bit integer.

Constraints

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 1000

• All the elements of nums are unique.

• 1 <= target <= 1000

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : O(T * N), T be the target value, and N be the 
 *    number of elements in the input array.
 * Space complexity : O(T)
 */

class Solution {
    private HashMap<Integer, Integer> memo;

    public int combinationSum4(int[] nums, int target) {
        // minor optimization
        // Arrays.sort(nums);
        memo = new HashMap<>();
        return combs(nums, target);
    }

    private int combs(int[] nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.containsKey(remain))
            return memo.get(remain);

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
            // minor optimizaton, early stopping
            // else
            //     break;
        }
        memo.put(remain, result);
        return result;
    }
}

Solution 2

/**
 * Time complexity : O(T * N), T be the target value, and N be the 
 *    number of elements in the input array.
 * Space complexity : O(T)
 */

class Solution {
    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];
    }
}

Follow up