问题概述：
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. 回溯法的模板
(全子集， 加入解)
判断是否停止
（最终解， 加入解）
向下搜索
遍历条件：
判断是否需要剪枝，忽略
改变状态
向下搜索
改回状态，方便下一个遍历
No comments:
Post a Comment