问题概述:
DFS(深度优先搜索)要解决的问题之一为搜索所有的可能的解(all possible solutions).
一般来说,当涉及到“所有”的时候, 有两种问题:
1. 枚举所有的子集 ( enumerate all subsets)
时间复杂度
有组合[1, 2, 3], 那么他的子集数目为 空集 ([ ])+ 其他所有子集。 其他所有子集为是否选取元素i: True or False. 那么 如果有N个元素, 则时间复杂度为2^N.
则具体的个数为2^N+1个组合。
那么具体到时间复杂度则为给出每一个解得时间复杂度 X 总的解得个数: N2^N
具体的例题
Subsets
Given a set of distinct integers, return all possible subsets.
Notice
Elements in a subset must be innon-descendingorder.
The solution set must not contain duplicate subsets.
Example
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
分析:
当给定一个空集来生成所有的子集时:
【】
【1】 【2】 【3】
【1,2】 【1,3】 【2,3】
【1,2,3】
搜索生成 1-》 1,2-》 1,2,3 达成终止条件, 1, 3 达成终止条件,返回, 2, 2,3 终止, 3
class Solution {
public:
vector < vector < int >> subsets(vector < int > & nums) {
// write your code here
vector < vector < int >> results;
vector < int > solution;
//确保是升序
sort(nums.begin(), nums.end());
helper(results, solution, nums, 0);
return results;
}
void helper(vector < vector < int >> & results, vector < int > & solution, vector < int > & nums, int ind) {
// add one solution
// 如果是所有子集,先加入collection 再判断终止
results.push_back(solution);
// stop searching
if (ind >= nums.size())
return;
// continue to search
for (int i = ind; i < nums.size(); i++) {
solution.push_back(nums[i]);
// 更新solution并向下搜索
helper(results, solution, nums, i + 1);
// 返回到之前状态,向下一个状态搜索
solution.pop_back();
}
}
};
那么对于深搜所有子集问题
1 push 当前解
2 判断是否应该终止搜索
3. 对于从当前层数(位置)开始往后的其他所有状态
a) 判断是否更新当前解
b) 向下搜索
c) 恢复更新
Subsets II
Given a list of numbers that may has duplicate numbers, return all possible subsets
Notice
Each element in a subset must be innon-descendingorder.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.
分析:
此题与上题的区别为有重复元素出现, 所以过程中需要剪枝。
例如 【1, 2, 2】
第一次 为【1】 【2】 【2x】 (我们不需要两个2)
第二次为【1】 -》 【1, 2】【1,2 X】 (不需要两个【1,2】)
那么我们知道当元素出现重复的时候只需要取一个,关键是取第一个2还是第二个2?
需要一个例子 【1, 2, 2】 是有效的子集,那么如果取了第二个2,则不会出现
所以, a[i] == a[i-1]; continue; 为这里的剪枝部分
具体实现如下:
class Solution {
public:
/*
* @param nums: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector < vector < int >> subsetsWithDup(vector < int > & nums) {
// write your code here
vector < vector < int >> results;
vector < int > solution;
sort(nums.begin(), nums.end());
helper(results, solution, nums, 0);
return results;
}
void helper(vector < vector < int >> & results, vector < int > & solution,
const vector < int > & nums, int ind) {
results.push_back(solution);
if (ind >= nums.size())
return;
for (int i = ind; i < nums.size(); i++) {
if (i != ind && nums[i] == nums[i - 1])
continue;
solution.push_back(nums[i]);
helper(results, solution, nums, i + 1);
solution.pop_back();
}
}
};
2. 枚举所有的组合 ( enumerate all combinations)
时间复杂度
有组合[1, 2, 3], 那么他的所有的permutation, 为
[1,2,3]
[ 2,1,3]
[2,1,3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
那么如何求得所有的permutation呢?
1, 2, 3
1, 2, 3 -> 1, 2, 3 | 1, 3, 2
2, 1, 3 -> 2, 1, 3 | 2, 3, 1
3, 2, 1 -> 3 , 2, 1 | 3, 1, 2
可以看出 a0 与 [a0....an] swap后,继续向下搜索即可,算是一个完美的递归问题
具体的例题
Given a list of numbers, return all possible permutations.
Example
For nums = [1,2,3], the permutations are:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
如上面分析, 每一个给定初始子集给与后,需要把a0 与[a0.... an]互换后向下搜索, 所以DFS条件就完美形成了。 注意的是向下搜索的时候不是搜索当前遍历的元素,而是搜索下一个index应该填入什么。 这个和全子集问题不同,全子集问题搜索的是选取不选取遍历的元素, 所以一个是更新了当前选取的元素并下下一个元素搜索, 一个是更新了当前状态,并向下一个状态搜索。
class Solution {
public:
/*
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector < vector < int >> permute(vector < int > & nums) {
// write your code here
vector < vector < int >> results;
helper(results, nums, 0);
return results;
}
void helper(vector < vector < int >> & results, vector < int > & nums, int ind) {
if (ind >= nums.size()) {
results.push_back(nums);
return;
}
for (int i = ind; i < nums.size(); i++) {
swap(nums[i], nums[ind]);
helper(results, nums, ind + 1);
swap(nums[i], nums[ind]);
}
}
};
Permutation II
Given a list of numbers with duplicate number in it. Find allunique permutations.
Example
For numbers [1,2,2] the unique permutations are:
[
[1,2,2],
[2,1,2],
[2,2,1]
]
分析:
第一次互换:
1,2,2 -》 1 -- 2,2 | 2 --1,2 | 2 --1,2
我们发现1 与 2互换了两次, 那么我们应该如何剪枝?
剪第一个2还是第二个2?
如果减掉第二个2, 则 2--1,2 向下发展 2 -- 1 ---2, 2-- 2---1
如果减掉第二个2, 结果是一样的
所以就这个问题而言, 1, 只需要和同样的数字互换一次即可。 但是具体操作如何实现?
因为中间过程中我们用了多次互换, 很难再用a[i] == a[i-1]这种小技巧了。 那么最优的办法是只和最后一次出现的数字换。 为什么不和最先一次的数字互换? 如果写完题目会发现从当前位置向前查找非常昂贵, 而向下查找非常便宜。
class Solution {
public:
/*
* @param : A list of integers
* @return: A list of unique permutations
*/
vector < vector < int >> permuteUnique(vector < int > & nums) {
// write your code here
vector < vector < int >> results;
permute(results, nums, 0);
return results;
}
void permute(vector < vector < int >> & results, vector < int > & nums, int ind) {
if (ind >= nums.size()) {
results.push_back(nums);
return;
}
for (int i = ind; i < nums.size(); i++) {
bool found = false;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] == nums[i]) {
found = true;
break;
}
}
if (found)
continue;
swap(nums[i], nums[ind]);
permute(results, nums, ind + 1);
swap(nums[i], nums[ind]);
}
}
};
总结
1. All possible solutions 问题着重于解决2^n, n!的问题, 对于2^n的问题,是解决的各个元素选取与不选取的问题,中间过程的解均为全解的一部分。 而n!的问题为解决解得第i个元素应该对应给定的原第j个元素对其并向下搜索问题, 每次搜索触底后才算一个最终解。 所以我们会发现2^n问题是每次都会把初始子集加入解,判断终止, 并向下搜索, 而n!为判断终止后加入解。
results.push_back(solution); if stop ; vs if stop result.push_back(solution)
2. 对于剪枝的问题,或者去掉重复问题,具体问题具体分析, 有可能是用第一个,有可能用最后一个,这个要在纸上画清楚
3. 回溯法的模板
(全子集, 加入解)
判断是否停止
(最终解, 加入解)
向下搜索
遍历条件:
判断是否需要剪枝,忽略
改变状态
向下搜索
改回状态,方便下一个遍历