LeetCode Q 377 - Combination Sum IV

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?

Solution :

Solution 1: DP

State Transfer Function:
dp[i] += dp[i - num], where num belongs to nums.

Time Complexity: O(n * t)
Space Complexity: O(t)

Code:

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 = 1; i <= target; i++) {
		for (int num: nums) {
			if (i >= num) dp[i] += dp[i - num];
		}
	}
	return dp[target];
}

Solution 2: Recursion + HashMap

Code:

Map<Integer, Integer> map = new HashMap<>();
public int combinationSum4(int[] nums, int target) {
	int count = 0;
	if (nums == null || nums.length ==0 || target < 0 ) return 0;
	if ( target == 0 ) return 1;
	if (map.containsKey(target)) return map.get(target);
	for (int num: nums)
	    count += combinationSum4(nums, target - num);
	map.put(target, count);
	return count;
}

Follow up:

In order to allow negative integers, the length of the combination sum needs to be restricted, or the search will not stop. We need to use memory to avoid repeated calculations.

In order to solve this question, we use backtrack with memory. In Word Breaker II, we also use backtrack + memory method.

Code: Backtrack with memorizing

public int combinationSum42(int[] nums, int target, int MaxLen) {
	if (nums == null || nums.length ==0 || MaxLen <= 0 ) return 0;
	map2 = new HashMap<>();
	return helper2(nums, 0, target, MaxLen);
}

Map<Integer, Map<Integer,Integer>> map2 = new HashMap<>();
private int helper2(int[] nums, int len, int target, int MaxLen) {
	int count = 0;
	if (len > MaxLen) return 0;

	if (map2.containsKey(target) && map2.get(target).containsKey(len))
		return map2.get(target).get(len);
	
	if ( target == 0 )   count++;
	
	for (int num: nums) 
		count+= helper2(nums, len+1, target-num, MaxLen);

	if (!map2.containsKey(target)) 
		map2.put(target, new HashMap<Integer,Integer>());
	Map<Integer,Integer> memo = map2.get(target);

	memo.put(len, count);
	return count;
}

Reprint policy