1，組合
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
dfs(n, k, 1);
return res;
}
//n表示從1-n里面選，k表示要選多少個(gè)數(shù)荐绝，start表示選擇的起點(diǎn)
void dfs(int n, int k, int start) {
//剪枝拓挥，如果path加上起點(diǎn)到終點(diǎn)的長度還是小于k的話，不可能構(gòu)造成功
if (path.size() + n - start + 1 < k) return;
if (path.size() == k) {
res.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
dfs(n, k, i + 1);
path.pop_back();
}
}
};
class Solution {
public:
vector<string> res;
//每個(gè)數(shù)字的組合情況
string strs[10] = {
" ", " ", "abc",
"def", "ghi", "jkl",
"mno", "pqrs", "tuv",
"wxyz"};
vector<string> letterCombinations(string digits) {
if (digits.empty()) return res;
dfs(digits, 0, "");
return res;
}
//u表示當(dāng)前第幾位碴萧，path表示當(dāng)前的路徑
void dfs(string digits, int u, string path) {
if (u == digits.size()) res.push_back(path);
else {
//遍歷這一位可以取哪些字符
for (auto str : strs[digits[u] - '0']) {
dfs(digits, u + 1, path + str);
}
}
}
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum(vector<int>& c, int t) {
dfs(c, 0, t);
return res;
}
//u表示當(dāng)前枚舉到第幾個(gè)數(shù)乙嘀，t表示還差多少
void dfs(vector<int> &c, int u, int t) {
if (!t) {
res.push_back(path);
return;
}
if (u == c.size()) return;
//枚舉當(dāng)前的數(shù)選幾個(gè)
for (int i = 0; i * c[u] <= t; i++) {
dfs(c, u + 1, t - i * c[u]);
path.push_back(c[u]);
}
//恢復(fù)現(xiàn)場
for (int i = 0; i * c[u] <= t; i++)
path.pop_back();
}
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum2(vector<int>& c, int t) {
//排序末购，為了方便統(tǒng)計(jì)重復(fù)數(shù)字的個(gè)數(shù)
sort(c.begin(), c.end());
dfs(c, 0, t);
return res;
}
//u表示當(dāng)前枚舉到第幾個(gè)數(shù)，t表示還剩多少
void dfs(vector<int> &c, int u, int t) {
if (!t) {
res.push_back(path);
return;
}
if (u == c.size()) return;
int k = u + 1;
while (k < c.size() && c[k] == c[u]) k++;
//統(tǒng)計(jì)個(gè)數(shù)
int cnt = k - u;
for (int i = 0; i * c[u] <= t && i <= cnt; i++) {
dfs(c, k, t - i * c[u]);
path.push_back(c[u]);
}
//恢復(fù)現(xiàn)場
for (int i = 0; i * c[u] <= t && i <= cnt; i++)
path.pop_back();
}
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(1, n, k);
return res;
}
//u表示當(dāng)前是第幾個(gè)數(shù)虎谢，n表示還差多少盟榴，k表示還剩的個(gè)數(shù)
void dfs(int u, int n, int k) {
//如果當(dāng)前和已經(jīng)等于n
if (!n) {
//如果恰好是k個(gè)數(shù)
if (!k) res.push_back(path);
//當(dāng)前和沒有到n，個(gè)數(shù)也沒有到k
} else if (k) {
//當(dāng)前數(shù)從u開始選
for (int i = u; i <= 9; i++) {
//如果當(dāng)前數(shù)小于等于n
if (n >= i) {
//選i
path.push_back(i);
//枚舉下一個(gè)數(shù)
dfs(i + 1, n - i, k - 1);
//恢復(fù)現(xiàn)場
path.pop_back();
}
}
}
}
};
2婴噩，分割
class Solution {
public:
vector<vector<bool>> f;
vector<vector<string>> res;
vector<string> path;
vector<vector<string>> partition(string s) {
int n = s.size();
//f[i][j]表示i~j是回文串
f = vector<vector<bool>> (n, vector<bool> (n));
for (int j = 0; j < n; j++)
for (int i = 0; i <= j; i++) {
//如果只有一個(gè)字符擎场，是回文串
if (i == j) f[i][j] = true;
else if (s[i] == s[j]) {
//如果是兩個(gè)字符或者i+1~j-1是回文串，i~j就也是回文串
if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
}
}
//暴搜
dfs(s, 0);
return res;
}
//u表示第幾個(gè)字符
void dfs(string s, int u) {
if (u == s.size()) {
res.push_back(path);
}
else {
for (int i = u; i < s.size(); i++) {
//如果u~i是回文串几莽，記錄迅办，并搜索下一個(gè)字母
if (f[u][i]) {
path.push_back(s.substr(u, i - u + 1));
dfs(s, i + 1);
path.pop_back();
}
}
}
}
};
93. 復(fù)原 IP 地址 - 力扣（LeetCode）
class Solution {
public:
vector<string> res;
vector<string> restoreIpAddresses(string s) {
dfs(s, 0, 0, "");
return res;
}
//u表示s的第u位，k表示第k個(gè)數(shù)
void dfs(string& s, int u, int k, string path) {
//如果搜到s的最后一位章蚣，并且是第四個(gè)數(shù)站欺，保存答案
if (u == s.size()) {
if (k == 4) {
path.pop_back();
res.push_back(path);
}
return;
}
//如果超過四個(gè)數(shù)，直接返回
if (k == 4) return;
//從第u位開始搜纤垂，t用來記錄數(shù)值
for (int i = u, t = 0; i < s.size(); i++) {
//如果有前導(dǎo)零就break
if (i > u && s[u] == '0') break;
t = t * 10 + s[i] - '0';
//如果t在0-255之內(nèi)就搜下一層
if (t <= 255) {
dfs(s, i + 1, k + 1, path + to_string(t) + '.');
}
//否則矾策，break
else break;
}
}
};
3，子集
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return res;
}
//u表示當(dāng)前是第幾個(gè)數(shù)
void dfs(vector<int>& nums, int u) {
//因?yàn)橐涗涀蛹吐伲圆挥玫鹊絬==n的時(shí)候再加入答案
res.push_back(path);
for (int i = u; i < nums.size(); i++) {
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(nums, 0);
return res;
}
//u表示當(dāng)前是第幾位
void dfs(vector<int>& nums, int u) {
//如果枚舉到最后一位就返回答案
if (u == nums.size()) {
res.push_back(path);
return;
}
int k = u + 1;
//統(tǒng)計(jì)重復(fù)元素的個(gè)數(shù)
while (k < nums.size() && nums[u] == nums[k]) k++;
//將重復(fù)元素枚舉
for (int i = 0; i <= k - u; i++) {
dfs(nums, k);
path.push_back(nums[u]);
}
//恢復(fù)現(xiàn)場
for (int i = 0; i <= k - u; i++)
path.pop_back();
}
};
4贾虽，排列
class Solution {
public:
//記錄第i個(gè)位置的狀態(tài)
vector<bool> st;
vector<int> path;
vector<vector<int>> result;
void dfs(vector<int>& nums, int u) {
//如果第u個(gè)位置已經(jīng)等于數(shù)組長度，說明列舉完了
if (u == nums.size()) {
result.push_back(path);
return;
}
//從第一個(gè)位置開始枚舉
for (int i = 0; i < nums.size(); i++) {
//如果第i個(gè)位置沒有放元素
if (!st[i]) {
path[u] = nums[i];
st[i] = true;
dfs(nums, u + 1);
st[i] = false;
path[u] = -1;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
st = vector<bool> (n);
path = vector<int> (n);
dfs(nums, 0);
return result;
}
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<bool> st;
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
st = vector<bool>(n);
path = vector<int>(n);
//排序吼鱼，用來判重
sort(nums.begin(), nums.end());
dfs(nums, 0);
return res;
}
//u表示枚舉第幾位
void dfs(vector<int>& nums, int u) {
if (u == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!st[i]) {
//如果有重復(fù)元素蓬豁，只用第一個(gè)
if (i && nums[i] == nums[i - 1] && !st[i - 1]) continue;
path[u] = nums[i];
st[i] = true;
dfs(nums, u + 1);
st[i] = false;
}
}
}
};
5，棋盤問題
class Solution {
public:
vector<bool> col, dg, udg;
vector<vector<string>> res;
vector<string> path;
int n;
vector<vector<string>> solveNQueens(int _n) {
n = _n;
col = vector<bool> (n);
dg = udg = vector<bool> (2 * n);
path = vector<string> (n, string(n, '.'));
dfs(0);
return res;
}
//全排列的思想菇肃，u表示第幾行
void dfs(int u) {
if (u == n) {
res.push_back(path);
return;
}
for (int i = 0; i < n; i++) {
//如果第i列庆尘，對角線，反對角線都沒有放置皇后
if (!col[i] && !dg[u - i + n] && !udg[u + i]) {
path[u][i] = 'Q';
col[i] = dg[u - i + n] = udg[u + i] = true;
dfs(u + 1);
col[i] = dg[u - i + n] = udg[u + i] = false;
path[u][i] = '.';
}
}
}
};
37. 解數(shù)獨(dú) - 力扣（LeetCode）
class Solution {
public:
bool row[9][9], col[9][9], cell[3][3][9];
void solveSudoku(vector<vector<char>>& board) {
memset(row, 0, sizeof row);
memset(col, 0, sizeof col);
memset(cell, 0, sizeof cell);
int n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
//如果board[i][j] != '.'巷送，記錄當(dāng)前位置為true
if (board[i][j] != '.') {
int t = board[i][j] - '1';
row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
}
}
//從0驶忌，0開始搜索
dfs(board, 0, 0);
}
//x表示第幾行，y表示第幾列
bool dfs(vector<vector<char>>& board, int x, int y) {
//如果這一列搜索完笑跛，就搜索下一行
if (y == 9) x++, y = 0;
//如果搜索完付魔，返回true
if (x == 9) return true;
//如果當(dāng)前值不為'.'，搜索下一行
if (board[x][y] != '.') return dfs(board, x, y + 1);
for (int i = 0; i < 9; i++) {
//如果當(dāng)前行列都沒有出現(xiàn)數(shù)字
if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
board[x][y] = '1' + i;
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
if (dfs(board, x, y + 1)) return true;
board[x][y] = '.';
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
}
}
return false;
}
};
6飞蹂，其他
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> findSubsequences(vector<int>& nums) {
dfs(nums, 0);
return res;
}
//st表示當(dāng)前開始的位置
void dfs(vector<int>& nums, int st) {
//如果path的長度大于等于2几苍，加入答案
if (path.size() >= 2) res.push_back(path);
if (st == nums.size()) return;
//哈希表記錄當(dāng)前數(shù)是否已經(jīng)用過
unordered_set<int> S;
for (int i = st; i < nums.size(); i++) {
//如果path為空，或者當(dāng)前數(shù)大于path的最后一個(gè)數(shù)陈哑，看是否需要加入path
if (path.empty() || nums[i] >= path.back()) {
//如果已經(jīng)用過妻坝，跳過
if (S.count(nums[i])) continue;
//加入哈希表和答案
S.insert(nums[i]);
path.push_back(nums[i]);
//搜索下一個(gè)數(shù)
dfs(nums, i + 1);
path.pop_back();
}
}
}
};
class Solution {
public:
unordered_map<string, multiset<string>> g;
vector<string> ans;
vector<string> findItinerary(vector<vector<string>>& tickets) {
for (auto &t : tickets) g[t[0]].insert(t[1]);
dfs("JFK");
return vector<string>(ans.rbegin(), ans.rend());
}
void dfs(string ver) {
while (g[ver].size()) {
string next = *g[ver].begin();
g[ver].erase(g[ver].begin());
dfs(next);
}
ans.push_back(ver);
}
};
