创作不易，感谢支持!!!
一、电话号码的组合
. - 力扣（LeetCode）
class Solution {
public:
string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string path;//记录路径
vector<string> ret;//记录返回值
vector<string> letterCombinations(string digits)
{
if(digits.size()==0) return ret;
dfs(digits,0);
return ret;
}
void dfs(string &digits,int pos)
{
if(path.size()==digits.size()) {ret.push_back(path);return;}
for(auto ch:hash[digits[pos]-'0'])//从当前位置开始遍历，然后再去下一个里面找
{
path.push_back(ch);
dfs(digits,pos+1);
path.pop_back();
}
}
};二、括号生成
. - 力扣（LeetCode）
class Solution {
public:
vector<string> ret;
string path;
int n;
vector<string> generateParenthesis(int _n)
{
n=_n;
dfs(0,0);
return ret;
}
void dfs(int open,int close)//open和close记录上界和下界
{
if(path.size()==2*n) {ret.push_back(path);return;}
if(open<n)
{
path.push_back('(');
dfs(open+1,close);
path.pop_back();
}
if(close<open)
{
path.push_back(')');
dfs(open,close+1);
path.pop_back();
}
}
};三、组合
. - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
int k;//用k全局，可以减少一个参数
int n;//用n全局，可以减少一个参数
vector<vector<int>> combine(int _n, int _k)
{
k=_k;
n=_n;
dfs(1);
return ret;
}
void dfs(int pos)
{
if(path.size()==k) {ret.push_back(path);return;}
for(int i=pos;i<=n;++i)
{
path.push_back(i);
dfs(i+1);
path.pop_back();
}
}
};四、目标和
. - 力扣（LeetCode）
class Solution {
int ret=0;//记录返回结果
public:
int findTargetSumWays(vector<int>& nums, int target)
{
dfs(nums,target,0,0);
return ret;
}
void dfs(vector<int>& nums, int target,int index,int sum)
{
if(index==nums.size())
{
if(sum==target) ++ret;
}
//选正数
else
{
dfs(nums,target,index+1,sum+nums[index]);
dfs(nums,target,index+1,sum-nums[index]);
}
}
};五、组合总和I
. - 力扣（LeetCode）
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
dfs(candidates,0,target);
return ret;
}
void dfs(vector<int>& candidates,int pos,int target)
{
if(target==0){ ret.push_back(path);return;}
if(target<0) return;
for(int i=pos;i<candidates.size();++i)//第一层，遍历每个数
{
path.push_back(candidates[i]);
dfs(candidates,i,target-candidates[i]);//要从原先的位置去找
path.pop_back();
}
}
};
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
dfs(candidates,0,target);
return ret;
}
void dfs(vector<int>& nums,int pos,int target)
{
if(target==0){ ret.push_back(path);return;}
if(target<0||pos==nums.size()) return;
for(int k=0;k*nums[pos]<=target;++k)//第一层，遍历每个数
{
if(k) path.push_back(nums[pos]);
dfs(nums,pos+1,target-k*nums[pos]);//要从原先的位置去找
}
for(int k=1;k*nums[pos]<=target;++k) path.pop_back();//
}
};六、组合总和II
. - 力扣（LeetCode）
七、组合总和III
. - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> ret;//记录组合
vector<int> path;//记录路径
vector<vector<int>> combinationSum3(int k, int n) {
if(n>45) return ret;//剪枝
dfs(k,n,1);
return ret;
}
void dfs(int k,int n,int pos)
{
if(k==0&&n==0)
{
ret.push_back(path);
return;
}
if(n<0||k<0) return;
for(int i=pos;i<=9;++i)
{
path.push_back(i);
dfs(k-1,n-i,i+1);
path.pop_back();
}
}
};八、组合总和IV
. - 力扣（LeetCode）
该题和前面是类似的，但是用回溯算法，会超时
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int& num : nums) {
if (num <= i&& dp[i - num] < INT_MAX - dp[i])
{
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}; 