一、搜索问题

几乎所有的搜索问题都适用使用排列组合模板

模板：　

　　要返回的结果

　　异常处理‘

　　调用helper(找到所有【】开头的子集，放到results里）

　　递归函数：

　　　　递归三要素：

　　　　　　1、递归的定义（接受什么样的参数，返回什么结果，做了什么事情）--找到所有以subset开头的子集，然后丢到results里

　　　　　　2、递归拆解  ----   //deepcopy   //reference  for()循环，先加，递归，移除　　　　

　　　　　　3、递归出口 ----自然而然的return

 

组合：T（n） = O(答案个数*构造每个答案的时间) = O(n * 2ⁿ)

1、题目子集：给定一个含不同整数的集合，返回其所有的子集，

如果 S = [1,2,3]，有如下的解：

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

 

2、permutations（排列）：T（n） = O(n * S) = O（n*n!）,S是所有的答案个数

题目：给定一个数字列表，返回其所有可能的排列。

样例

给出一个列表[1,2,3]，其全排列为：

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

 

 

　　　　　　

dfs:从空集出发，不撞墙不回头

　　从空集出发，先添加第一个，然后第二个....,没有可再加的了，去掉新添加的元素，依次向上返回，.....直到可以向下添加没添加的元素。

bfs:以空集