能用宽搜的,一般都直接用宽搜
BFS: 由点及面,分层的遍历,简单的图的最短路径。
什么时候用DFS:找所有方案的题,一定是DFS, 90% DFS的题,要么是排列,要么是组合

Combination 组合

时间复杂度可能与2^n相关.

递归三要素:

  • 递归的定义(做了设么事情,返回什么值,接收什么参数)
  • 递归的拆解
  • 递归的出口

Permutation 排列

复杂度与n!相关,因为排列的总共个数是n!那么多个

1
2
3
4
5
6
7
def dfs(self, nums, path, result):
if nums == []:
result += [path] # 没有其他候选者了
for i in xrange(len(nums)):
new_path = path + [nums[i]] # 当前的节点
candicates = nums[0:i] + nums[i+1:]Œ†Ÿœ€ # 除去当前的数的其他候选者,这个时候candicates已经减少了。所以就会递归到下一层
self.dfs(candicates, new_path, result)

permutations 2:
注意一点,就是在helper函数里面,处理的都是candicates, 不是nums。这个非常重要。这样才能有效的递归下去
去重的话,就是看i>0并且candicates[i]==candicates[i-1]的时候continue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
"""
@param: : A list of integers
@return: A list of unique permutations
"""


def permuteUnique(self, nums):
# write your code here
result = []
if not nums:
return [[]]
nums.sort()
length = len(nums)
def helper(current, candicates):
if candicates == []:
result.append(current)
for i in xrange(len(candicates)):
if i > 0 and candicates[i] == candicates[i-1]:
continue
num = candicates[i]
xcurrent = current + [num]
print xcurrent
helper(xcurrent, candicates[0:i]+candicates[i+1:])
helper([], nums)
return result

Non-Recursion

几个程序必须背下来

  • TreeTraversal(tree preorder, inorder, postorder)
  • TreeTraversal(binary search tree interator)
  • combination
  • permutation

subsets

  • 要所有子集,可以认为是,分成以1开头的子集合,以2开头的子集合,以3开头的子集合。
  • 分成1开头的子集合,可以再分以 1,2开头的子集合,以1,3开头的子集合
  • 这样就行程了一个回溯树,比如到了1,2,3之后,到底,把3 pop 出来,再去访问 [1, 3]

小计硬币组合问题

def (x, y, z, n)
设计这样一个方法,x, y, z分别为手里持有的一元,五角,一角的数量,n为需要的总的钱数,返回最少的硬币组合

  • 开始以为这个就是一个dfs的问题,所以用dfs来做,用了好几层循环,可以达到目的
  • 最后发现这个其实是一个小学题目.只需要确定最多能用多少一元,花完一元最多能用多少五角,花完五角最多能用多少一角就可以 一元数量n / x, 五角数量n%x/y, 一角数量n%x%y/z