This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res = {{}};
for (int i=0 ; i<nums.size() ; i++){
int s = res.size();
for(int j=0 ; j<s ; j++){
res.push_back(res[j]);
res.back().push_back(nums[i]);
}
}
return res;
}
};
class Solution {
public:
void solve(vector<vector<int>> &res, vector<int> ph, vector<int>& nums, int begin){
res.push_back(ph);
for(int i=begin ; i<nums.size() ; i++){
if(i > begin && nums[i]==nums[i-1]){
continue;
}
ph.push_back(nums[i]);
solve(res, ph, nums, i+1);
ph.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> ph;
solve(res, ph, nums, 0);
return res;
}
};
class Solution {
public:
void solve(vector<vector<int>> &res, vector<int> placeHolder, vector<int>& nums){
if(placeHolder.size()==nums.size()){
res.push_back(placeHolder);
}
else{
for(int i=0 ; i<nums.size() ; i++){
if (find(placeHolder.begin(), placeHolder.end(), nums[i]) != placeHolder.end()) continue;
placeHolder.push_back(nums[i]);
solve(res, placeHolder, nums);
placeHolder.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> placeHolder;
solve(res, placeHolder, nums);
return res;
}
};
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& ph, vector<int>& nums, vector<bool>& used) {
if (ph.size() == nums.size()) {
res.push_back(ph);
}
else {
for (int i = 0; i < nums.size(); i++) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])){
continue;
}
used[i] = true;
ph.push_back(nums[i]);
backtrack(res, ph, nums, used);
used[i] = false;
ph.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
vector<int> ph;
backtrack(res, ph, nums, used);
return res;
}
};
class Solution {
private:
void combination(vector<int>& candidates, int target, vector<int>& currComb, int currSum, int index, vector<vector<int>>& res) {
if (currSum == target) {
res.push_back(currComb);
return;
}
if (currSum > target || index >= candidates.size()) {
return;
}
for (int i = index; i < candidates.size(); i++) {
currComb.push_back(candidates[i]);
currSum += candidates[i];
combination(candidates, target, currComb, currSum, i, res);
currComb.pop_back();
currSum -= candidates[i];
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> currComb;
combination(candidates, target, currComb, 0, 0, res);
return res;
}
};
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& ph, vector<int>& nums, long remain, int start) {
if (remain < 0) {
return;
}
else if (remain == 0) {
res.push_back(ph);
}
else {
for (int i = start; i < nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
ph.push_back(nums[i]);
backtrack(res, ph, nums, remain - nums[i], i + 1);
ph.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
vector<int> ph;
backtrack(res, ph, nums, target, 0);
return res;
}
};
class Solution {
public:
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
void solve(vector<vector<string>>& res, vector<string>& ph, const string& s, int begin) {
if (begin >= s.length()) {
res.push_back(ph);
}
else {
for (int i = begin; i < s.length(); i++) {
if (isPalindrome(s, begin, i)) {
ph.push_back(s.substr(begin, i - begin + 1));
solve(res, ph, s, i + 1);
ph.pop_back();
}
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> ph;
solve(res, ph, s, 0);
return res;
}
};
class Solution {
unordered_map<int, string> pad{
{2, "abc"},
{3, "def"},
{4, "ghi"},
{5, "jkl"},
{6, "mno"},
{7, "pqrs"},
{8, "tuv"},
{9, "wxyz"},
};
public:
void solve(vector<string>& res, string& ph, const string& digits, int begin) {
if (begin >= digits.length()) {
res.push_back(ph);
}
else {
int digit = digits[begin] - '0';
for (char c : pad[digit]) {
ph += c;
solve(res, ph, digits, begin + 1);
ph.pop_back();
}
}
}
vector<string> letterCombinations(const string& digits) {
vector<string> res;
string ph;
if (!digits.empty()) {
solve(res, ph, digits, 0);
}
return res;
}
};