本文内容是基于小象学院——林沐 《面试算法 LeetCode 刷题班》，后期仍将对相关内容进行不定期更新！
4. 递归，回溯，分治
文章目录
LeetCode 78 求子级（M）
给定一个不含重复数的集合，求所有不重复的子集
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> item;
result.push_back(item);
generate(0,nums,item,result);
return result;
}
void generate(int i, vector<int> & nums, vector<int> &item, vector<vector<int>> &result) {
if (nums.size()==i)
{
return;
}
item.push_back(nums[i]);
result.push_back(item);
generate(i + 1, nums, item, result);
item.pop_back();
generate(i + 1, nums, item, result);
}
};
LeetCode 90 求子集2（M）
给定一个含重复数的集合，求所有不重复的子集
set（<set>） 和 sort（<algorithm>）
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
vector<int> item;
result.push_back(item);
set<vector<int>> res_set;
sort(nums.begin(), nums.end());
generate(0, nums, item, result,res_set);
return result;
}
void generate(int i, vector<int> & nums, vector<int> &item, vector<vector<int>> &result, set<vector<int>> &res_set) {
if (nums.size() == i)
{
return;
}
item.push_back(nums[i]);
if (res_set.find(item) == res_set.end())
{ result.push_back(item);
res_set.insert(item);
}
generate(i + 1, nums, item, result,res_set);
item.pop_back();
generate(i + 1, nums, item, result,res_set);
}
};
LeetCode 40 组合数之和2（M）
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
vector<vector<int>> result;
vector<int> item;
set<vector<int>> res_set;
sort(nums.begin(), nums.end());
generate(0, nums, item, 0,target,result, res_set);
return result;
}
void generate(int i, vector<int> & nums, vector<int> &item,int sum, int target,vector<vector<int>> &result, set<vector<int>> &res_set) {
if (nums.size() == i || sum>target)
{
return;
}
sum += nums[i];
item.push_back(nums[i]);
if ( sum == target && res_set.find(item) == res_set.end())
{
result.push_back(item);
res_set.insert(item);
}
generate(i + 1, nums, item, sum,target,result, res_set);
item.pop_back();
sum -= nums[i];
generate(i + 1, nums, item, sum,target,result, res_set);
}
};
LeetCode 22 生成括号（M）
给定n对括号，首先递归生成所有可能的合法的括号组合。代码如下：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string item="";
generate(item, n, n,result);
return result;
}
void generate(string item, int left,int right, vector<string> &result)
{
if (left==0 && right ==0)
{
result.push_back(item);
return;
}
if (left>0)
{
generate(item + "(", left-1, right, result);
}
if (right>left)
{
generate(item + ")", left, right-1, result);
}
}
};
在这个的基础上进行规律筛选。
LeetCode 51 N 皇后（H）
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<vector<int>> mark;
vector<string> location;
for (int i = 0; i < n; i++) // 创建nxn的矩阵，n列
{
mark.push_back(vector<int>()); // 先压入一个空vector，相当于行，然后在其基础上添加内容
for (int j = 0; j < n; j++) { // 每一行有n个元素
mark[i].push_back(0); // 均初始化为 0
}
location.push_back(""); // 先压入一个空字符串，然后在其基础上添加内容
location[i].append(n, '.'); // 初始化 location 为 "...." x 4
} // 初始化完毕
generate(0, n, location, result, mark); // 进入递归
return result;
}
void put_down_the_queen(int x, int y, vector<vector<int>> &mark) {
static const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}; // 方向数组，x部分
static const int dy[] = {0,0,-1,1,-1,1,-1,1}; // 方向数组，y部分
mark[x][y] = 1;
for (int i = 1; i < mark.size(); i++) {
for (int j = 0; j < 8; j++) {
int new_x = x + i*dx[j];
int new_y = y + i*dy[j];
if (new_x<mark.size() && new_x>=0 && new_y>=0 && new_y<mark.size())
{
mark[new_x][new_y] = 1;
}
}
}
}
void generate(int k, int n, vector<string> &location,vector<vector<string>> &result, vector<vector<int>> &mark) {
if (k==n)
{
result.push_back(location);
return;
}
for (int i = 0; i < n; i++) {
if (mark[k][i] == 0) // 只找每一行为0的位置
{
vector<vector<int>> tmp_mark = mark; // 保留放置此皇后时的状态，留作回溯用
location[k][i] = 'Q'; // 将是0的位置放入皇后'Q'
put_down_the_queen(k, i, mark); // 依次向外延伸，将满足条件的皇后延长线的数字都变为1
generate(k + 1, n, location, result, mark); // 然后递归进入下一行，进行皇后放置和修改整个数组状态，如果找不到直接返回到上一个状态，继续运行下面的语句
mark = tmp_mark; // 返回上一个状态
location[k][i] = '.'; //位置也返回上一个状态
}
}
}
};
LeetCode 315 逆序数（H）
预备知识，两个数组的归并排序：
class Solution {
public:
void merge_sort_two_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, vector<int> &vec) {
int i = 0;
int j = 0;
while (i<sub_vec1.size() && j< sub_vec2.size())
{
if (sub_vec1[i] < sub_vec2[j])
{
vec.push_back(sub_vec1[i]);
i++;
}
else
{
vec.push_back(sub_vec2[j]);
j++;
}
}
for(;i<sub_vec1.size();i++)
vec.push_back(sub_vec1[i]);
for(;j<sub_vec2.size();j++)
vec.push_back(sub_vec2[j]);
}
};
预备知识，一个数组的归并排序（nlogn）：
分治，将一个规模为N的问题，分解为K个规模较小的子问题，这些问题相互独立与原问题性质相同。求出后再进行合并。
class Solution {
public:
void merge_sort_two_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, vector<int> &vec) {
int i = 0;
int j = 0;
while (i<sub_vec1.size() && j< sub_vec2.size())
{
if (sub_vec1[i] < sub_vec2[j])
{
vec.push_back(sub_vec1[i]);
i++;
}
else
{
vec.push_back(sub_vec2[j]);
j++;
}
}
for(;i<sub_vec1.size();i++)
vec.push_back(sub_vec1[i]);
for(;j<sub_vec2.size();j++)
vec.push_back(sub_vec2[j]);
}
void merge_sort(vector<int> &vec) { // 分治函数
if (vec.size()<2)
{
return;
}
int mid = vec.size() / 2;
vector<int> sub_vec1;
vector<int> sub_vec2;
for (int i = 0; i < mid;i++) {
sub_vec1.push_back(vec[i]);
}
for (int i = mid; i < vec.size(); i++) {
sub_vec2.push_back(vec[i]);
}
merge_sort(sub_vec1);
merge_sort(sub_vec2);
vec.clear();
merge_sort_two_vec(sub_vec1, sub_vec2, vec);
}
};
问题：
class Solution {
public:
vector<int> countSmaller(vector<int> &nums)
{
vector<pair<int, int>> vec;
vector<int> count;
for (int i = 0; i < nums.size(); i++)
{
vec.push_back(make_pair(nums[i], i));
count.push_back(0);
}
merge_sort(vec, count);
return count;
}
void merge_sort_two_vec(vector<pair<int,int>> &sub_vec1, vector<pair<int,int>> &sub_vec2, vector<pair<int,int>> &vec,vector<int>&count) {
int i = 0;
int j = 0;
while (i<sub_vec1.size() && j< sub_vec2.size())
{
if (sub_vec1[i].first <= sub_vec2[j].first)
{
count[sub_vec1[i].second]+=j;
vec.push_back(sub_vec1[i]);
i++;
}
else
{
vec.push_back(sub_vec2[j]);
j++;
}
}
for(;i<sub_vec1.size();i++)
{
count[sub_vec1[i].second]+=j;
vec.push_back(sub_vec1[i]);
}
for(;j<sub_vec2.size();j++)
vec.push_back(sub_vec2[j]);
}
void merge_sort(vector<pair<int,int>> &vec, vector<int> & count) {
if (vec.size()<2)
{
return;
}
int mid = vec.size() / 2;
vector<pair<int,int>> sub_vec1;
vector<pair<int, int>> sub_vec2;
for (int i = 0; i < mid;i++) {
sub_vec1.push_back(vec[i]);
}
for (int i = mid; i < vec.size(); i++) {
sub_vec2.push_back(vec[i]);
}
merge_sort(sub_vec1,count);
merge_sort(sub_vec2,count);
vec.clear();
merge_sort_two_vec(sub_vec1, sub_vec2, vec,count);
}
};