子集问题-LeetCode 78、52（无重复子集，N皇后II）
子集问题-LeetCode 78、52（无重复子集，N皇后II）
作者：TeddyZhang，公众号：算法工程师之路
回溯问题：LeetCode #51
1
编程题
【LeetCode #78】子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例:
输入: nums = [1,2,3] 输出:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
解题思路：
我们首先新建一个vector，初始化存在一个空的列表，然后我们每次复制当前res中的所有元素，并且对其加入新元素，加入到res中去，从res的长度逐渐增加！但是很不容易想到这么巧的思路！ 因此：
第一个for循环，循环nums中所有数字元素，用于新数字每次添加！ 第二个for循环，循环当前res中所有的元素，与新数字合并后添加到res中去！
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > res();
for(int i=;i<nums.size();i++){
int cnt=res.size();
for(int j=;j<cnt;j++){
vector<int> tmp=res[j];
tmp.push_back(nums[i]);
res.push_back(tmp);
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subsets
【LeetCode #52】N皇后 II
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。
[ [".Q..", // 解法 1 "…Q", "Q…", "..Q."], ["..Q.", // 解法 2 "Q…", "…Q", ".Q.."] ]
解题思路：
昨天分享的N皇后再复习一遍，觉得LeetCode顺序有问题，明明N皇后比N皇后 II要难，并且这个题目的还有一种更快速的解法，使用一种位运算的方法，但有点复杂，大家可以到LeetCode官网上查看，我觉得回溯的思路更容易理解！！！
class Solution {
public:
void solve(vector<bool>& cols_, vector<bool>& diag1s_, vector<bool>& diag2s_, int n, int row){
if(row == n){
count ++;
return;
}
for(auto col = ; col < n; col++){
int ll = row + col;
int rr = row - col + n - ;
if (cols_[col] && diag1s_[ll] && diag2s_[rr]){
cols_[col] = false;
diag1s_[ll] = false;
diag2s_[rr] = false;
solve(cols_, diag1s_, diag2s_, n, row+);
cols_[col] = true;
diag1s_[ll] = true;
diag2s_[rr] = true;
}
}
}
int totalNQueens(int n) {
vector<bool> cols_(n, true);
vector<bool> diag1s_(*n-1, true);
vector<bool> diag2s_(*n-1, true);
solve(cols_, diag1s_, diag2s_, n, );
return count;
}
private:
int count = ;
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens-ii