题目
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
思路
和组合总和的思路一致，都是根据加和来控制递归的深度
class Solution {
public:
vector<vector<int>> res;
vector<int> elem;
bool IsINRes(vector<int> elem2)
{
for(int i = 0; i < res.size(); ++i)
{
if(res[i].size() == elem2.size())
{
sort(elem2.begin(), elem2.end());
sort(res[i].begin(), res[i].end());
int j;
for(j = 0; j < elem.size(); ++j)
{
if(elem2[j] != res[i][j]) break;
}
if(j == elem2.size()) return true;
}
}
return false;
}
void combinationSum2Aux(vector<int>& candidates, int target, int start_index)
{
for(int i = start_index; i < candidates.size(); ++i)
{
if(target - candidates[i] < 0)
{
return;
}
else if(target - candidates[i] == 0)
{
elem.emplace_back(candidates[i]);
if(!IsINRes(elem)) res.emplace_back(elem);
elem.pop_back();
return;
}
else
{
elem.emplace_back(candidates[i]);
combinationSum2Aux(candidates, target - candidates[i], i + 1);
elem.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
combinationSum2Aux(candidates, target, 0);
return res;
}
};
细节还是重复元素这里，使用和组合总和一样的方法，超出时间限制了
ok，使用unordered_map来识别重复元素
struct VectorHash {
size_t operator()(const std::vector<int>& v) const {
return 1;
}
};
struct AlwaysUnequal {
bool operator()(const std::vector<int>& v, const std::vector<int>& v2) const {
//cout << "v:" << v[0] << " compare " << "v2:" << v2[0] << endl;
unordered_map<int, int> compare;
unordered_map<int, int> compare2;
if(v.size() == v2.size())
{
for(int i = 0; i < v.size(); ++i)
{
compare[v[i]]++;
compare2[v2[i]]++;
}
if(compare.size() != compare2.size()) return false;
for(auto& iter : compare)
{
if(compare2[iter.first] != iter.second) return false;
}
return true;
}
return false;
}
};
class Solution {
public:
unordered_set<vector<int>, VectorHash, AlwaysUnequal> res;
vector<int> elem;
void combinationSum2Aux(vector<int>& candidates, int target, int start_index)
{
for(int i = start_index; i < candidates.size(); ++i)
{
if(target - candidates[i] < 0)
{
return;
}
else if(target - candidates[i] == 0)
{
elem.emplace_back(candidates[i]);
res.insert(elem);
elem.pop_back();
return;
}
else
{
elem.emplace_back(candidates[i]);
combinationSum2Aux(candidates, target - candidates[i], i + 1);
elem.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
combinationSum2Aux(candidates, target, 0);
vector<vector<int>> res_vec;
for(auto elem : res)
{
res_vec.emplace_back(elem);
}
return res_vec;
}
};
对于unordered_set的理解
std::unordered_set是C++标准库中的一个容器，它提供了存储唯一元素的集合，这些元素是无序的。unordered_set的工作机制基于哈希表，它使用哈希函数来快速定位元素的存储位置。以下是unordered_set的基本机制：
- 哈希函数：当您向
unordered_set添加一个元素时，它会使用哈希函数来计算该元素的哈希值。这个哈希值决定了元素在内部存储桶数组中的位置。 - 等价比较：如果两个元素的哈希值相同，
unordered_set会使用等价比较函数来判断这两个元素是否相等。如果等价比较函数确定它们不相等，unordered_set会在相同的存储桶位置存储这两个元素。 - 冲突解决：当多个元素具有相同的哈希值时，会发生哈希冲突。
unordered_set通过链表或其他方法来解决冲突，允许多个元素存在于同一个存储桶中。
VectorHash是一个自定义的哈希函数，它为vector<int>类型的元素提供了哈希值。AlwaysUnequal是一个自定义的等价比较函数，它总是返回false，这意味着即使两个vector<int>的哈希值相同，unordered_set也会认为它们是不同的元素，并将它们都存储在集合中。
依然超时
看过代码随想录，接着整
class Solution {
public:
vector<vector<int>> res;
vector<int> elem;
void combinationSum2Aux(vector<int>& candidates, int target, int start_index)
{
for(int i = start_index; i < candidates.size(); ++i)
{
if(i > start_index && candidates[i] == candidates[i - 1]) continue;
if(target - candidates[i] < 0)
{
return;
}
else if(target - candidates[i] == 0)
{
elem.emplace_back(candidates[i]);
res.emplace_back(elem);
elem.pop_back();
return;
}
else
{
elem.emplace_back(candidates[i]);
combinationSum2Aux(candidates, target - candidates[i], i + 1);
elem.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
combinationSum2Aux(candidates, target, 0);
return res;
}
};
if(i > start_index && candidates[i] == candidates[i - 1]) continue;
只添加了一行代码，解决了所有问题，对于原理不清楚