【每日刷题】Day133
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. LCR 085. 括号生成 - 力扣（LeetCode）
2. LCR 102. 目标和 - 力扣（LeetCode）
3. LCR 081. 组合总和 - 力扣（LeetCode）
1. LCR 085. 括号生成 - 力扣（LeetCode）
//思路：深搜+回溯。
//画出决策树
class Solution {
public:
vector<string> ans;
string tmp;
int left = 0,right = 0;
void dfs(int n)
{
if(right==n)
{
ans.push_back(tmp);
return;
}
if(left<n)//左括号路径深搜，当left == n时，不能继续如'('，去到下面入')'
{
tmp.push_back('(');
left++;
dfs(n);
tmp.pop_back();
left--;
}
if(right<left&&right<n)//这里多一个条件，')'的数量不能超过 '('，否则会有多余的')'无法匹配
{
tmp.push_back(')');
right++;
dfs(n);
tmp.pop_back();
right--;
}
}
vector<string> generateParenthesis(int n)
{
dfs(n);
return ans;
}
};
2. LCR 102. 目标和 - 力扣（LeetCode）
//思路：暴搜+深搜+回溯
//画出决策树
class Solution {
public:
int ans = 0;
void dfs(vector<int>& nums, int target, int i,int sum)
{
if(i==nums.size())
{
if(sum==target) ans++;
return;
}
//前序遍历
dfs(nums,target,i+1,sum+nums[i]);
dfs(nums,target,i+1,sum-nums[i]);
}
int findTargetSumWays(vector<int>& nums, int target)
{
dfs(nums,target,0,0);
return ans;
}
};
3. LCR 081. 组合总和 - 力扣（LeetCode）
//思路：暴搜+深搜+回溯
//画出决策树
//本题思路与 Day 125 中的 "组合" 完全类似，这里直接引用 Day 125 的决策树
//不同的是， "组合" 中的回溯条件为 组合的子数组长度 == k。
//而本题的回溯条件是 组合的子数组的数组和 == target，无非也就是多了一个记录数组和的sum 变量
//不过还有一个回溯条件，就是 sum >target
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
bool hash[31];
void dfs(vector<int>& candidates, int target,int sum)
{
if(sum>target) return;
if(sum==target)//回溯
{
ans.push_back(tmp);//记录
return;
}
for(int i = 0;i<candidates.size();i++)
{
//下面代码与 "组合" 完全类似，只多了一个 sum 记录数组和
if(hash[i]) continue;
tmp.push_back(candidates[i]);
for(int j = i-1;j>=0;j--) hash[j] = true;
dfs(candidates,target,sum+candidates[i]);
tmp.pop_back();
for(int m = i-1;m>=0;m--) hash[m] = false;
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
dfs(candidates,target,0);
return ans;
}
};
