递归
(1)子集
方式一：递归算法
class Solution {
public:
void generator(int i, vector<int>& nums, vector<int>& item, vector<vector<int>>& result)
{
if( i >= nums.size() ) // 递归终止条件
{
return ;
}
item.push_back(nums[i]); // 生成子集
result.push_back(item); // 将子集push入result
generator(i+1, nums, item, result); // 第一次递归调用
item.pop_back(); // 将子集中最后一个元素弹出
generator(i+1, nums, item, result); // 第二次递归调用
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result; // 存储最终的结果
vector<int> item; // 回溯时，产生各个子集的数组
result.push_back(item); // 将空集push入result
generator(0, nums, item, result ); // 计算各个子集
return result;
}
};
方式二：位运算算法
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
int max_set = 1<<nums.size(); // nums.size()个数即有2的num.size()次方个组合方式
for(int i=0; i<max_set; ++i) // 生成每种组合
{
vector<int> item;
for(int j=0; j<nums.size(); ++j) // 生成每个item
{
if( i & (1<<j) )
{
item.push_back(nums[j]);
}
}
result.push_back(item);
}
return result;
}
};
（2）子集II
方法一：递归算法
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
vector<int>item;
set<vector<int>> set_item;
sort(nums.begin(), nums.end()); // 排序
result.push_back(item);
generator(0, nums, item, result, set_item);
return result;
}
void generator(int k, vector<int>& nums, vector<int>& item, vector<vector<int>>& result, set<vector<int>>& set_item)
{
if( k >= nums.size())
{
return ;
}
item.push_back(nums[k]);
if( set_item.find(item) == set_item.end() ) // 去重
{
result.push_back(item);
set_item.insert(item);
}
generator(k+1, nums, item, result, set_item);
item.pop_back();
generator(k+1, nums, item, result, set_item);
}
};
方法二：位运算
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先排序
vector<vector<int>> result;
int max_set = 1<<nums.size();
set<vector<int>> m_result;
for(int i=0; i<max_set; ++i)
{
vector<int> item;
for(int j=0; j<nums.size(); ++j)
{
if( i & 1<<j )
{
item.push_back(nums[j]);
}
}
m_result.insert(item); // 去重
}
for(set<vector<int>>::iterator it=m_result.begin(); it!=m_result.end(); ++it)
{
result.push_back(*it);
}
return result;
}
};
（3）组合总和 II
递归剪枝：
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> item;
set<vector<int>> set_item;
sort(candidates.begin(), candidates.end()); // 排序
generator(0, candidates, target, item, result, set_item, 0);
return result;
}
void generator(int k, vector<int>& candidates, int target, vector<int>& item,
vector<vector<int>>& result, set<vector<int>>& set_item, int sum) // 添加一个sum元素，用来判断是否大于target
{
if((k >= candidates.size()) || sum > target) // 若sum > target则，直接return（剪枝）
{
return ;
}
sum += candidates[k];
item.push_back(candidates[k]);
if((sum == target) && (set_item.find(item) == set_item.end()))
{
result.push_back(item);
set_item.insert(item);
}
generator(k+1, candidates, target, item, result, set_item, sum);
sum -= candidates[k]; // 回溯时，将sum中的candidates[i]减一
item.pop_back();
generator(k+1, candidates, target, item, result, set_item, sum);
}
};
(4)括号生成
递归限制条件：
- 左括号与右括号的数量，最多放置n个；
- 若左括号的数量小于等于右括号的数量，不可进行右括号的递归。
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
generator("", n, 0, 0, result);
return result;
}
void generator(string item, int n, int left, int right, vector<string>& result)
{
if( 2*n == item.size() || right > left )
{
if( left == n && right == n )
{
result.push_back(item);
}
return ;
}
generator(item + '(', n, left+1, right, result);
generator(item + ')', n, left, right+1, result);
}
};
(5)N皇后
设置方向数组：
方向数组示意图
在(x,y)处放置皇后后，棋盘mark[n][n]的状态更新函数：
// 第x行，y列放置皇后， 更新棋盘上的状态，
// mark[行][列]表示一张棋盘
void put_down_the_queue(int x, int y, vector<vector<int>>& mark)
{
static const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}; // 方向数组，dx与dy一一对应
static const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
mark[x][y] = 1; // (x, y)处放置皇后，进行标记
for(int i=1; i<mark.size(); i++) // 8个方向，每个方向向外延伸1至N-1
{
for(int j=0; j<8; j++)
{
int new_x = x + i * dx[j]; // 更新x方向
int new_y = y + i * dy[j]; // 更新y方向
}
if( (new_x >= 0 && new_x < mark.size())
&& (new_y >= 0 && new_y < mark.size()) ) // 检查新位置是否在棋盘上
{
mark[new_x][new_y] = 1; // 将新位置标记为1
}
}
}
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result; // 存放结果
vector<vector<int>> mark; // 棋盘状态
vector<string> location; // 存放某个摆放结果，当完成一次递归找到结果后，将location pushi进入 result
// 初始化mark和location
for(int i=0; i<n; i++)
{
mark.push_back(vector<int>());
for(int j=0; j<n; ++j)
{
mark[i].push_back(0);
}
location.push_back("");
location[i].append(n, '.');
}
generator(0, n, mark, location, result);
return result;
}
void generator(int k, // k表示第k+1个皇后（因为k是从0开始）
int n, // 总共需要放n个皇后
vector<vector<int>>& mark, // 棋盘状态
vector<string>& location, // 放入第k+1个皇后时的皇后摆放状态
vector<vector<string>>& result) // 存放的结果
{
if( k == n ) // 皇后摆放完成后
{
result.push_back(location); // 将摆放位置push入result中
return ;
}
for(int i=0; i<n; ++i)
{
if( mark[k][i] == 0 ) // 表示此位置可以放置皇后
{
vector<vector<int>> tmp_mark = mark; // 建立临时tmp_mark
put_queen_in_mark(k, i, mark); // 更新mark状态
location[k][i] = 'Q'; // 更新location状态
generator(k+1, n, mark, location, result); // 递归调用
mark = tmp_mark; // 回溯后，改变mark的状态
location[k][i] = '.'; // 回溯后，改变location的状态
}
}
}
void put_queen_in_mark(int x, int y, vector<vector<int>>& mark) // 更新mark的状态
{
static const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
static const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
mark[x][y] = 1;
for(int i=0; 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>=0 && new_x<mark.size()) && (new_y>=0 && new_y<mark.size()) )
{
mark[new_x][new_y] = 1;
}
}
}
}
};
