rainyzz's blog

回溯法

从Subsets说起,给定一个集合,比如说[1,2,3],要输出其所有子集合。当然有许多方法了,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(S == null || S.length == 0) return result;
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(S);
helper(result,list,S,0);
return result;
}
public void helper(List<List<Integer>> result,
List<Integer> list, int[] S, int end){
result.add(new ArrayList(list));
for(int i = end; i < S.length; i++){
list.add(S[i]);
helper(result,list,S,i+1);
list.remove(list.size() - 1);
}
}
}

回溯法相当于在结果的空间里进行深度遍历,从最顶端的空集开始,先加入1,变成[1],然后加入2,变成[1,2],加入3,变成[1,2,3],函数结束回到上一层,去掉3,回到[1,2],发现也不能加新的,然后再去掉2,然后再加入3,变成[1,3],最后再向上走,去掉3,加入2,成为[1,2],继续之前的动作。这个从最底层的结果逐步往上找寻新结果的过程就是回溯法。

这个子集合的问题是最通用的一个回溯问题,对于其他可以使用回溯的问题,不同的地方只是体现在什么时候应该加入结果集合,什么时候应该进入下一层以及什么时候应该往上回溯。