[LeetCode] 377. Combination Sum IV

轉自LeetCode

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.

 

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

 

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

39. Combination Sum 的衍生題

求排列組合，第一個想到的就是 DFS

然後可以看到 (1,1,2) 和 (2,1,1) 被視作不同的答案

直接用 DFS 求會 TLE，所以借用個 HashMap 來剪枝

如果 map 裡面已經有答案了，就回傳答案，不用再找下去

kotlin

	class Solution {
	private val map = hashMapOf<Int,Int>()
	fun combinationSum4(nums: IntArray, target: Int): Int {
	return dfs(nums, target)
	}
	fun dfs(nums: IntArray, target: Int): Int {
	if(target == 0) {
	return 1
	}
	if(map[target] != null) {
	return map[target]!!
	}
	var total = 0
	for(n in nums) {
	if(target - n >= 0) {
	total += dfs(nums, target - n)
	}
	}
	map[target] = total
	return total
	}
	}

view raw combination_sum_IV.kt hosted with ❤ by GitHub