C++遡及法剪定による組合せ数の和
18422 ワード
繰り返し要素があるグループ数が知られており、このグループ数で構成できるすべてのサブセット、サブセットの各要素と整数targetのサブセットを求め、結果には繰り返しのサブセットがない.例えばnums[]=[10,1,2,7,6,1,5],target=8の結果は,[[1,7],[1,2,5],[2,6],[1,1,6]]この問題は遡及法またはビット演算アルゴリズムにかかわらず,全体の時間複雑度はO(2^n)である.時間の複雑さを低減するために、遡及検索中に枝切り操作を行う必要があります.再帰呼び出し時に、選択した要素の和sumを計算します.sum>targetの場合、より深い検索を行わずに、直接戻ります.
実行結果:
ここでは元の数を逆順に並べてから枝切り遡及を行ってもよい.ただ
に改心
逆シーケンスに変更された実行結果は、次のとおりです.
#include
#include
class Solution
{
public:
Solution() {};
~Solution() {};
std::vector<std::vector<int>> combinationSum2
(std::vector<int>& candidates, int target)
{
std::vector<std::vector<int>> result;
std::vector<int> item;
std::sort(candidates.begin(), candidates.end());
generate(0, candidates, result, item, 0, target);
return result;
}
private:
void generate(int i, std::vector<int>& nums, std::vector<std::vector<int>>& result, std::vector<int> item,
int sum, int target)
{
if (i>=nums.size()||sum>target)
{
return;
}
sum += nums[i];
item.push_back(nums[i]);
if (sum==target&&find(result.begin(),result.end(),item)==result.end())
{
result.push_back(item);
}
generate(i + 1, nums, result, item, sum, target);
sum -= nums[i];
item.pop_back();
generate(i + 1, nums, result, item, sum, target);
}
};
int main()
{
std::vector<int> nums;
nums.push_back(10);
nums.push_back(1);
nums.push_back(2);
nums.push_back(7);
nums.push_back(6);
nums.push_back(1);
nums.push_back(5);
std::vector<std::vector<int>> result;
Solution solve;
result = solve.combinationSum2(nums, 8);
for (unsigned int i = 0; i < result.size(); i++)
{
if (result[i].size()==0)
{
printf("[]");
}
for (unsigned int j = 0; j < result[i].size(); j++)
{
printf("[%d]", result[i][j]);
}
printf("
");
}
return 0;
}
実行結果:
[1][1][6]
[1][2][5]
[1][7]
[2][6]
ここでは元の数を逆順に並べてから枝切り遡及を行ってもよい.ただ
std::sort(candidates.begin(), candidates.end());
に改心
std::sort(candidates.rbegin(), candidates.rend());
逆シーケンスに変更された実行結果は、次のとおりです.
[7][1]
[6][2]
[6][1][1]
[5][2][1]