框架
回溯算法中需要考虑到的问题
- 路径,选择列表,结束条件
结束条件
// 结束条件:已经处理完所有数
if (track.size() == nums.length) {
// 处理逻辑
}
// 结束条件:已经处理完所有球
if (index == nums.length) {
// 处理逻辑
}
class Solution {
public:
bool dfs(vector<int>& nums, int index, vector<int>& v, int target){
if(index == nums.size()){
return true;
}
for(int i = 0; i < v.size(); ++i){
//若不进行此步优化,则超时
if(i && v[i] == v[i - 1]){
continue;
}
v[i] += nums[index];
if(v[i] <= target && dfs(nums, index + 1, v, target)){
return true;
}
v[i] -= nums[index];
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % k != 0){
return false;
}
sort(nums.begin(), nums.end(), greater<int>());
vector<int> v(k);
return dfs(nums, 0 , v, sum / k);
}
};
class Solution {
public:
bool dfs(int index, vector<int>& matchsticks, vector<int>& edges, int len){
if(index == matchsticks.size()){
return true;
}
for(int i = 0; i < edges.size(); i++){
edges[i] += matchsticks[index];
if(edges[i] <= len && dfs(index + 1, matchsticks, edges, len)){
return true;
}
edges[i] -= matchsticks[index];
}
return false;
}
bool makesquare(vector<int>& matchsticks) {
int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
if(sum % 4 != 0){
return false;
}
//降序排序
sort(matchsticks.begin(), matchsticks.end(), greater<int>());
vector<int> edges(4);
return dfs(0, matchsticks, edges, sum / 4);
}
};
标签:index,return,nums,int,sum,matchsticks,算法,回溯,集合
From: https://www.cnblogs.com/changebaobao/p/16712632.html