题目

解析

17. Letter Combinations of a Phone Number

39. Combination Sum

we need to avoid duplicates, e.g., [2,2,3] and [3,2,2] are the same
- how to achieve:
  - in our decision tree, one branch is to include the current element ([2,2]), and another branch is not to include the current element ([2])
  - i.e., 可不可以在搜索的时候就去重呢？答案是可以的。遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。具体的做法是：每一次搜索的时候设置下一轮搜索的起点 begin
Base case:
- total == target -> found a combination
- begin >= len(candidates) or total > target -> cannot find any combination
复杂度分析
- 时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 $O(n * 2^n)$ 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 $target−candidates[idx]≥0$ 进行剪枝，所以实际运行情况是远远小于这个上界的。
- 空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target)层。

# - time: O(2^target) ??
# - space: O(1) (不考虑调用栈所占用的内存空间 和 结果所占用的空间)
	def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
		res = []

		def dfs(begin, cur, total):
			# begin is a pointer, and we only consider [i, len(candidates)) from candidates
			if total == target:  # find a combination
				res.append(cur.copy())  # couldn't directly use cur, since we still use cur later
				return
			if begin >= len(candidates) or total > target:  # cannot find any combination
				return

			cur.append(candidates[begin])
			dfs(begin, cur, total + candidates[begin])
			cur.pop()
			dfs(begin + 1, cur, total)

		dfs(0, [], 0)
		return res

Ref

40. Combination Sum II

46. Permutations

复杂度分析

时间复杂度：$O(n×n!)$，其中 n 为序列的长度。
- 时间复杂度和数组排列的方案数成线性关系，方案数为 $N×(N−1)×(N−2)…×2×1$，即复杂度为 $O(N!)$ ；数组旋转操作使用 $O(N)$ ；因此总体时间复杂度为 O(N!N)O(N!N)O(N!N) 。
空间复杂度：O(n)，其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。

	def permute(self, nums: List[int]) -> List[List[int]]:
		res = []

		if len(nums) == 1:
			return [nums.copy()]

		for _ in range(len(nums)):  # run n times
			n = nums.pop(0)  # remove the first element from nums

			perms = self.permute(nums)
			for perm in perms:
				perm.append(n)
			res.extend(perms)

			nums.append(n)  # append the removed element to the end

		return res

ref

78. Subsets

复杂度分析
- 时间复杂度：$O(n×2^n)$)。一共 $2^n$ 个状态，每种状态需要 O(n) 的时间来构造子集。
  - 在整个递归调用的过程中，start 是从小到大递增的，当 start 增加到 n 的时候，记录答案并终止递归。可以看出二进制枚举的时间复杂度是 $O(2^n)$
- 空间复杂度：O(n)，不考虑返回结果所占用的空间。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

# solution 1 - brute force (recursion)
# - time: O(n*2^n)
# - space: O(n)
	def subsets(self, nums: List[int]) -> List[List[int]]:
		res = []

		def backtracking(start, curSubsets):
			# to consider the elements in nums: [start, len(nums))
			if start >= len(nums):
				res.append(curSubsets.copy())
				return

			# case 1: decision to include nums[i]
			curSubsets.append(nums[start])
			backtracking(start + 1, curSubsets)

			# case 2: decision not to include nums[i]
			curSubsets.pop(-1)
			backtracking(start + 1, curSubsets)

		backtracking(0, [])
		return res

ref

[Notes] Backtracking（回溯）

题目

解析

17. Letter Combinations of a Phone Number

39. Combination Sum

40. Combination Sum II

46. Permutations

78. Subsets

79. Word Search

90. Subsets II

FEATURED TAGS

TOC