LeetCode之回溯法

46 全排列

可以往回回溯，即1-2-3，然后1-3-2

所以要用visited[]，不需要start

1
2
3
4
5
6
7
8
9


dfs(...) {
	for (int i = 0; ...) {
        if (!visited[i]) {
            添加
            dfs(...);
            撤销
        }
	}
}

78 子集

不能往回回溯，1-2-3和1-3-2是同样的子集，没有1-3-2

不需要用visited[]，用start变量，dfs(…, start)控制位置，保证后面的元素肯定在前面的元素后面

1
2
3
4
5
6
7


dfs(..., int start) {
	for (int i = start; ...) {
        添加
		dfs(..., i + 1);
        撤销
	}
}

39 组合总和

与78类似，不同的地方是后面的元素可以是前面的元素，即元素可以重复，唯一区别如下

1
2
3
4
5
6
7


dfs(..., int start) {
	for (int i = start; ...) {
        添加
		dfs(..., i); // 唯一区别在此
        撤销
	}
}

其中78和39也都可以用“选还是不选”的方法来做