LC 77. 组合
77. 组合 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
std::vector<int> tRes;
vector<vector<int>> res;
for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
{
for(int j = 0; j < n; j++) //遍历二进制的每一位 共n位
if(i & (1 << j))//判断二进制数字i的第j位是否存在
tRes.emplace_back(j+1);
if (tRes.size() == k) res.emplace_back(move(tRes));
tRes.clear();
}
res.shrink_to_fit();
return res;
}
};
// 参考模板 题解：https://zhuanlan.zhihu.com/p/406120574
LC 216.组合总和III
216. 组合总和 III - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
std::vector<int> tRes;
vector<vector<int>> res;
int sum = 0;
for(int i = 0; i < (1<<9); i++)
{
sum = 0;
for(int j = 0; j < 9; j++){
if(i & (1 << j)){
tRes.emplace_back(j+1);
sum += (j + 1);
}
}
if (tRes.size() == k && sum == n) res.emplace_back(move(tRes));
tRes.clear();
}
res.shrink_to_fit();
return res;
}
};
LC 17.电话号码的字母组合
17. 电话号码的字母组合 - 力扣（LeetCode）
class Solution {
public:
vector<string> res;
const string letterMap[10]{
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
void getCombinations(const string& digits,int index,const string &s){
if (index == digits.size()){
res.emplace_back(s);
return ;
}
int digit = digits[index] - '0';
string letter = letterMap[digit];
for (int i = 0; i < letter.size(); ++ i){
getCombinations(digits,index + 1,s + letter[i]);
}
}
vector<string> letterCombinations(string digits) {
res.clear();
if (digits.size() == 0) return res;
getCombinations(digits,0,"");
res.shrink_to_fit();
return res;
}
};
LC 39. 组合总和
39. 组合总和 - 力扣（LeetCode）
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int> & candidates,int target,int sum,int index){
if (sum == target){
res.emplace_back(path);
return;
}
for (int i = index; i < candidates.size() && sum + candidates[i] <= target; ++ i){
path.push_back(candidates[i]);
backtracking(candidates,target, sum + candidates[i],i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
path.clear();
res.clear();
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0);
res.shrink_to_fit();
return res;
}
};
LC 40.组合总和II
40. 组合总和 II - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int> &candidates, int target,int sum,int index){
if (sum == target){
res.emplace_back(path);
return ;
}
for (int i = index; i < candidates.size() && sum + candidates[i] <= target; ++i){
if (i > index && candidates[i] == candidates[i - 1]) continue;
path.push_back(candidates[i]);
backtracking(candidates,target,sum + candidates[i], i + 1);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
res.clear();
path.clear();
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0);
res.shrink_to_fit();
return res;
}
};
LC 131.分割回文串
131. 分割回文串 - 力扣（LeetCode）
class Solution {
public:
vector<string> path;
vector<vector<string>> res;
void backtracking(const string& s, int index){
if (index >= s.size()){
res.emplace_back(path);
return;
}
for(int i = index; i < s.size(); i++){
if (isPalindrome(s,index,i)){
string str = s.substr(index,i - index + 1);
path.emplace_back(str);
}
else{
continue;
}
backtracking(s,i + 1);
path.pop_back();
}
}
bool isPalindrome(const string &s, int startPos, int endPos){
for (int i = startPos,j = endPos; i < j; i ++,j --){
if (s[i] != s[j]){
return false;
}
}
return true;
}
vector<vector<string>> partition(string s) {
path.clear();
res.clear();
backtracking(s,0);
res.shrink_to_fit();
return res;
}
};
LC 93.复原IP地址
93. 复原 IP 地址 - 力扣（LeetCode）
class Solution {
public:
vector<string> res;
bool isValidAddr(const string& s, int startPos, int endPos){
if (startPos > endPos) return false;
if (s[startPos] == '0' && startPos != endPos) return false;
int num = 0;
for(int i = startPos; i <= endPos; i ++){
if (s[i] > '9' || s[i] < '0') return false;
num = num*10 + (s[i] - '0');
if (num > 255) return false;
}
return true;
}
void backtracking(string &s,int index,int posSum){
if (posSum == 3){
if (isValidAddr(s,index,s.size() - 1)) res.emplace_back(s);
return;
}
for(int i = index; i < s.size(); ++i){
if (isValidAddr(s,index,i)){
s.insert(s.begin() + i + 1,'.');
backtracking(s,i + 2,posSum + 1);
s.erase(s.begin() + i + 1);
} else break;
}
}
vector<string> restoreIpAddresses(string s) {
res.clear();
if (s.size() < 4 || s.size() > 12) return res;
backtracking(s,0,0);
res.shrink_to_fit();
return res;
}
};
LC 78.子集
78. 子集 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<int> tRes;
vector<vector<int>> res;
if (nums.size() == 1) {
res.emplace_back(tRes);
res.emplace_back(nums);
return res;
}
for(int i = 0; i < (1<<nums.size()); i++) //从0～2^n-1个状态
{
for(int j = 0; j < nums.size(); j++) //遍历二进制的每一位 共n位
if(i & (1 << j))//判断二进制数字i的第j位是否存在
tRes.emplace_back(nums[j]);
res.emplace_back(move(tRes));
tRes.clear();
}
res.shrink_to_fit();
return res;
}
};
LC 90.子集II
90. 子集 II - 力扣（LeetCode）
class Solution {
public:
bool hasRecord(const vector<vector<int>>& res, vector<int> t){
for(const vector<int> &ele : res)
if (ele == t) return true;
return false;
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
std::vector<int> tRes;
vector<vector<int>> res;
if (nums.size() == 1) {
res.emplace_back(tRes);
res.emplace_back(nums);
return res;
}
sort(nums.begin(),nums.end());
for(int i = 0; i < (1<<nums.size()); i++) //从0～2^n-1个状态
{
for(int j = 0; j < nums.size(); j++) //遍历二进制的每一位 共n位
if(i & (1 << j))//判断二进制数字i的第j位是否存在
tRes.emplace_back(nums[j]);
if (!hasRecord(res,tRes))
res.emplace_back(move(tRes));
tRes.clear();
}
res.shrink_to_fit();
return res;
}
};
LC 491.递增子序列
491. 非递减子序列 - 力扣（LeetCode）
class Solution {
public:
bool isAscSeque(const vector<int>& vec){
for(int i = 0,j = 1; i < vec.size() - 1; ++i,++j)
if (vec[i] > vec[j]) return false;
return true;
}
bool hasRecord(const vector<vector<int>>& res, const vector<int> &vec){
for(const vector<int>& ele : res)
if (ele == vec) return true;
return false;
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> res;
vector<int> tRes;
if (len < 2) return res;
for (int i = 0; i < (1 << len); ++ i){
for (int j = 0; j < len; ++ j){
if (i & (1 << j)){
tRes.emplace_back(nums[j]);
if (tRes.size() >= 2) {
if (!isAscSeque(tRes)){
tRes.clear();
break;
}
}
}
}
if(tRes.size() > 1 && isAscSeque(tRes) && !hasRecord(res,tRes)) res.emplace_back(tRes);
tRes.clear();
}
return res;
}
};
LC 46.全排列
46. 全排列 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums,vector<bool>& used)
{
if (path.size() == nums.size())
{
res.emplace_back(path);
return ;
}
for (int i = 0; i < nums.size(); ++ i)
{
if (used[i] == true) continue;
used[i] = true;
path.emplace_back(nums[i]);
backtracking(nums,used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(),false);
backtracking(nums,used);
res.shrink_to_fit();
return res;
}
};
LC 47.全排列 II
47. 全排列 II - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> res;
vector<int> tRes;
void backtracking(const vector<int>& nums,vector<bool>& used){
if (tRes.size() == nums.size()){
res.emplace_back(tRes);
return ;
}
for(int i = 0; i < nums.size(); ++ i){
if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;
if (!used[i])
{
used[i] = true;
tRes.emplace_back(nums[i]);
backtracking(nums,used);
tRes.pop_back();
used[i] = false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
res.clear();
tRes.clear();
if (nums.size() == 1){
res.emplace_back(nums);
return res;
}
sort(nums.begin(),nums.end());
vector<bool> used(nums.size());
backtracking(nums,used);
res.shrink_to_fit();
return res;
}
};
LC 51. N皇后
51. N 皇后 - 力扣（LeetCode）
class Solution {
public:
vector<vector<string>> res;
bool isValid(int row,int col,const vector<string>& chessboard,int n){
// 同行的列单元有无皇后
for (int i = 0; i < row; ++ i)
if (chessboard[i][col] == 'Q') return false;
// 棋盘左上顶点连线
for (int i = row - 1,j = col - 1; i >= 0&&j >= 0; -- i, --j)
if (chessboard[i][j] == 'Q') return false;
// 棋盘右上顶点连线
for (int i = row - 1,j = col + 1; i >= 0&&j < n; -- i, ++j)
if (chessboard[i][j] == 'Q') return false;
return true;
}
void backtracking(int n, int row, vector<string>& chessboard){
if (row == n){
res.emplace_back(chessboard);
return ;
}
for(int col = 0; col < n; ++ col){
if (isValid(row,col,chessboard,n)){
chessboard[row][col] = 'Q';
backtracking(n,row + 1,chessboard);
chessboard[row][col] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
res.clear();
vector<string> chessboard(n,string(n,'.'));
backtracking(n,0,chessboard);
res.shrink_to_fit();
return res;
}
};
LC 37. 解数独
37. 解数独 - 力扣（LeetCode）
class Solution {
public:
bool isValid(int row,int col, char val, vector<vector<char>>& board){
for(int i = 0; i < 9; ++ i)
if (board[row][i] == val) return false;
for(int i = 0; i < 9; ++ i)
if (board[i][col] == val) return false;
int cellStartRow = (row/3) *3;
int cellStartCol = (col/3) *3;
for (int i = cellStartRow; i < cellStartRow + 3; ++ i){
for (int j = cellStartCol; j < cellStartCol + 3; ++ j){
if (board[i][j] == val) return false;
}
}
return true;
}
bool backtracking(vector<vector<char>>& board){
for (int row = 0; row < 9; ++ row){
for(int col = 0; col < 9; ++ col){
if (board[row][col] == '.'){
for(char checkVal = '1'; checkVal <='9'; ++ checkVal){
if (isValid(row,col,checkVal,board)){
board[row][col] = checkVal;
if(backtracking(board)) return true;
board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
board.shrink_to_fit();
}
};
