Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, int n, int k, vector<int>& path, int ind){
if(path.size() == k){
ans.push_back(path);
return;
}
for(int i = ind; i <= n; i++){
path.push_back(i);
solve(ans, n, k, path, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
vector<int> path;
solve(ans, n, k, path, 1);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, int cur, int k, int n){
if(path.size() == k && n == 0){ // ending situation
ans.push_back(path);
return;
}
for(int i = cur; i <= 9; i++){
path.push_back(i);
solve(ans, path, i + 1, k, n - i);
path.pop_back(); // backtracking
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> path;
solve(ans, path, 1, k, n);
return ans;
}
};17. Letter Combinations of a Phone Number
Solution 1: #Backtracking
class Solution {
public:
string mp[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void solve(vector<string>& ans, string digits, string &cur_string){
if(digits == ""){ // edge case
ans.push_back(cur_string);
return;
}
int num = digits[0] - '0'; // get the current number
digits = digits.substr(1); // delete the first letter in digits
for(char c : mp[num]){
cur_string += c;
solve(ans, digits, cur_string);
cur_string.pop_back(); // backtracking
}
}
vector<string> letterCombinations(string digits) {
vector<string> ans;
if(digits == "") return ans;
string cur_string = "";
solve(ans, digits, cur_string);
return ans;
}
};Solution 2: #Recursion
class Solution {
public:
unordered_map<char, string> mp = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
void solve(string digits, int i, vector<string>& ans, string output){
if(i >= digits.size()){
ans.push_back(output);
return;
}
string temp = mp[digits[i]];
for(int j = 0; j < temp.size(); j++){
solve(digits, i + 1, ans, output + temp[j]);
}
}
vector<string> letterCombinations(string digits) {
vector<string> ans;
string output = "";
if(digits == "") return ans;
solve(digits, 0, ans, output);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, vector<int>& can, int start, int target){
if(target == 0){
ans.push_back(path);
return;
}
for(int i = start; i < can.size(); i++){ // remove duplicates
if(target >= can[i]){
path.push_back(can[i]);
solve(ans, path, can, i, target - can[i]); // remove duplicates
path.pop_back();
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
solve(ans, path, candidates, 0, target);
return ans;
}
};Solution 1: #Backtracking, 这题的重点是要在每层的递归树上面要做剪枝去重操作
class Solution {
public:
void solve(int id, vector<vector<int>>& ans, vector<int>& nums, vector<int>& path, int target){
if(target == 0){
ans.push_back(path);
return;
}
for(int i = id; i < nums.size(); i++){
if(nums[i] > target) break;
if(i > id && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
solve(i + 1, ans, nums, path, target - nums[i]);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> path;
vector<vector<int>> ans;
sort(candidates.begin(), candidates.end());
solve(0, ans, candidates, path, target);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
bool isPalindrome(string t){
int i = 0;
int j = t.size() - 1;
while(i < j){
if(t[i++] != t[j--]) return false;
}
return true;
}
void solve(vector<vector<string>>& ans, vector<string>& path, int idx, string s){
if(idx == s.size()){
ans.push_back(path);
return;
}
for(int i = idx; i < s.size(); i++){
if(isPalindrome(s.substr(idx, i - idx + 1))){
path.push_back(s.substr(idx, i - idx + 1));
solve(ans, path, i + 1, s); // 这里的参数注意是i + 1, 不要修改index位置
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> path;
solve(ans, path, 0, s);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
vector<string> ans;
void solve(string& s, string path, int index, int count){
if(count > 4) return;
if(count == 4 && index >= s.length()){
path.pop_back();
ans.push_back(path);
return;
}
for(int i = 1; i <= 3 && index + i <= s.length(); i++){
string num = s.substr(index, i);
if(num[0] == '0' && i != 1) break;
else if(stol(num) <= 255){
solve(s, path + s.substr(index, i) + ".", index + i, count + 1);
}
}
}
vector<string> restoreIpAddresses(string s) {
solve(s, "", 0, 0);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, vector<int>& nums, int idx){
int n = nums.size();
ans.push_back(path);
for(int i = idx; i < n; i++){
path.push_back(nums[i]);
solve(ans, path, nums, i + 1);
path.pop_back();
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
solve(ans, path, nums, 0);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, vector<int>& nums, int idx){
int n = nums.size();
if(idx >= n) return;
for(int i = idx; i < n; i++){
if(i > idx && nums[i] == nums[i - 1]) continue; // 同层级递归树剪枝
path.push_back(nums[i]);
ans.push_back(path);
solve(ans, path, nums, i + 1);
path.pop_back();
}
return;
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> path;
ans.push_back(path); // add NULL set
solve(ans, path, nums, 0);
return ans;
}
};491. Non-decreasing Subsequences
Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, vector<int>& nums, int idx){
if(path.size() >= 2) ans.push_back(path);
unordered_set<int> uset; // 用于当前层级的递归树去重
for(int i = idx; i < nums.size(); i++){
if((!path.empty() && path.back() > nums[i]) || uset.find(nums[i]) != uset.end()) continue;
path.push_back(nums[i]);
uset.insert(nums[i]); // 去重操作
solve(ans, path, nums, i + 1);
path.pop_back();
}
return;
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
solve(ans, path, nums, 0);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, vector<int>& nums, vector<bool> used){
if(path.size() == nums.size()){
ans.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++){
if(used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
solve(ans, path, nums, used);
used[i] = false;
path.pop_back();
}
return;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> path;
vector<bool> used(nums.size(), false);
solve(ans, path, nums, used);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& path, vector<int>& nums, vector<bool>& use){
if(path.size() == nums.size()){
ans.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++){
// 当前递归树层去重
if(use[i] || i > 0 && nums[i] == nums[i - 1] && !use[i - 1]) continue;
use[i] = true;
path.push_back(nums[i]);
solve(ans, path, nums, use);
path.pop_back();
use[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> path;
vector<bool> use(nums.size(), false);
solve(ans, path, nums, use);
return ans;
}
};Solution 1: #Backtracking, 欧拉图的一笔画问题，这里的回溯用bool因为只要找到一种条件满足即可
class Solution {
public:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool solve(int ticketNum, vector<string>& result){
if(result.size() == ticketNum + 1) return true;
// 注意引用！
for(pair<const string, int>& target : targets[result[result.size() - 1]]){
if(target.second > 0){
result.push_back(target.first);
target.second--;
if(solve(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
targets.clear();
vector<string> result;
for(const vector<string>& vec : tickets){
targets[vec[0]][vec[1]]++;
}
result.push_back("JFK");
solve(tickets.size(), result);
return result;
}
};Solution 1: #Backtracking
class Solution {
public:
vector<vector<string>> ans;
bool col[10], row[10], diag1[20], diag2[20];
void dfs(vector<string>& cur, int n){
if(cur.size() == n){
ans.push_back(cur);
return;
}
int i = cur.size();
cur.push_back(string(n, '.'));
for(int j = 0; j < n; j++){
if(!col[j] && !diag1[i - j + 8] && !diag2[i + j]){ // check col & diag
cur[i][j] = 'Q';
col[j] = diag1[i - j + 8] = diag2[i + j] = true;
dfs(cur, n);
cur[i][j] = '.';
col[j] = diag1[i - j + 8] = diag2[i + j] = false;
}
}
cur.pop_back();
}
vector<vector<string>> solveNQueens(int n) {
vector<string> cur;
dfs(cur, n);
return ans;
}
};Solution 1: #Backtracking
class Solution {
public:
bool isValid(int row, int col, char num, vector<vector<char>>& board){
for(int i = 0; i < 9; i++){ // 检查行
if(board[row][i] == num) return false;
}
for(int i = 0; i < 9; i++){ // 检查列
if(board[i][col] == num) return false;
}
int startRow = 3 * (row / 3); // sub-boxes的第一个点
int startCol = 3 * (col / 3);
for(int i = startRow; i < startRow + 3; i++){ // 检查sub-boxes
for(int j = startCol; j < startCol + 3; j++){
if(board[i][j] == num) return false;
}
}
return true;
}
bool solve(vector<vector<char>>& board){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] == '.'){
for(char k = '1'; k <= '9'; k++){
if(isValid(i, j, k, board)){
board[i][j] = k;
if(solve(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
};