KK's blog

LeetCode 377 Combination Sum IV

Posted on 2021-12-29 Edited on 2022-02-02 Disqus:

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

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?

题目大意：

求所有可能组合的和等于target。元素可以复用且顺序在组合中可以任意。

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列
LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题思路：

这题似组合又似排列，是组合的结果再全排列。求种数另一种的方法是DP. dp[n]为target=n所有的所有组合种数。属于数值->个数型DP
递归公式

1	dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]

解题步骤：

N/A

注意事项：

dp[i + nums[j]] += dp[i] 而不是dp[i] + 1
dp[0] = 1表示数值为0，可以不用任何数就能获得，所以是1种
先排序，否则如[3, 1, 2, 4]，返回dp[1] = 0, 但应该是dp[1] = 1

Python代码：

# dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]
def combinationSum4(self, nums: List[int], target: int) -> int:
	nums.sort() # remember
	dp = [0] * (target + 1)
	dp[0] = 1
	for i in range(len(dp)):
		for j in range(len(nums)):
			if i + nums[j] > target:
				break
			dp[i + nums[j]] += dp[i] # remember no +1
	return dp[-1]

算法分析：

时间复杂度为O(n*target)，空间复杂度O(target)

LeetCode 216 Combination Sum III

Posted on 2021-12-29 Disqus:

LeetCode

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used. Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

2 <= k <= 9 1 <= n <= 60

题目大意：

数字1-9的组合个数为k的组合和等于k，每个元素最多用一次

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

Leetcode 40和77的结合。个数和target都要达到。用if k == 0 and target == 0

Python代码：

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
	nums = [_ for _ in range(1, 10)]
	res = []
	self.dfs(nums, 0, k, n, [], res)
	return res

def dfs(self, nums, start, k, target, path, res):
	if k == 0 and target == 0:
		res.append(list(path))
		return
	if k == 0:
		return
	for i in range(start, len(nums)):
		path.append(nums[i])
		self.dfs(nums, i + 1, k - 1, target - nums[i], path, res)
		path.pop()

算法分析：

时间复杂度为O(2^k)，空间复杂度O(n)

LeetCode 077 Combinations

Posted on 2021-12-29 Disqus:

LeetCode

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

1 <= n <= 20 1 <= k <= n

题目大意：

求大小为k的所有可能组合

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

引入k作为模板API中的target，k为0作为终止条件。

Python代码：

def combine(self, n: int, k: int) -> List[List[int]]:
	nums = [_ for _ in range(1, n + 1)]
	path, result = [], []
	self.dfs(nums, 0, k, path, result)
	return result

def dfs(self, nums, st, k, path, result):
	if k == 0:
		result.append(list(path))
		return

	for i in range(st, len(nums)):
		path.append(nums[i])
		self.dfs(nums, i + 1, k - 1, path, result)
		path.pop()

算法分析：

时间复杂度为O(2^k)，空间复杂度O(n)

LeetCode 040 Combination Sum II

Posted on 2021-12-29 Disqus:

LeetCode

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100 1 <= candidates[i] <= 50
* 1 <= target <= 30

题目大意：

求组合和等于目标。元素不可复用且结果去重

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

类似于Leetcode 39，有两点不同。要去重，i > start并不是i > 0, 且比较前一个元素
因为元素不可重复，下一轮递归i + 1

Python代码：

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	candidates.sort()
	res = []
	self.dfs(candidates, 0, target, [], res)
	return list(res)

def dfs(self, candidates, start, target, path, res): # [1, 2], 0, 0, [1, 1], [1, 1]
	if target < 0:
		return
	if target == 0:
		res.append(list(path))
		return
	for i in range(start, len(candidates)): # [2]
		if i > start and candidates[i - 1] == candidates[i]:
			continue
		path.append(candidates[i]) # [1,1]
		self.dfs(candidates, i + 1, target - candidates[i], path, res)
		path.pop()

算法分析：

时间复杂度为O(2ⁿ)，空间复杂度O(n)

LeetCode 039 Combination Sum

Posted on 2021-12-29 Disqus:

LeetCode

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30 1 <= candidates[i] <= 200
All elements of candidates are distinct. 1 <= target <= 500

题目大意：

求组合和等于目标。元素可以复用

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

用标准组合模板dfs(self, candidates, start, target, path, res)，元素可以复用，所以下一轮递归从i开始
Python中path.pop()没有参数

Python代码：

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	candidates.sort()
	res = []
	self.dfs(candidates, 0, target, [], res)
	return res

def dfs(self, candidates, start, target, path, res): # [1, 2], 0, 0, [1, 1], [1, 1]
	if target < 0:
		return
	if target == 0:
		res.append(list(path))
		return
	for i in range(start, len(candidates)): # [2]
		path.append(candidates[i]) # [1,1]
		self.dfs(candidates, i, target - candidates[i], path, res)
		path.pop()

算法分析：

时间复杂度为O(2ⁿ)，空间复杂度O(n)