【LeetCode】90.サブセットII(C++)
1785 ワード
原題住所:https://leetcode-cn.com/problems/subsets-ii/submissions/
タイトルの説明:
重複要素を含む可能性のある整数配列numsを指定し、その配列のすべての可能なサブセット(べき乗セット)を返します.
説明:解セットに重複するサブセットを含めることはできません.
例:
入力:[1,2,2]出力:[[2],[1],[1,2,2],[1,2],[1,2],[]
問題解決方案:
この問題は最初はどうやって自分と通れないのか分からなかったが、ダイナミックな計画で書かなければならなかった.ルールは、i-1のサブセットをすべて追加してから、i-1のサブセットを追加する各セットの後ろにnums[i]を追加することですが、ダイナミックプランニングが難しく、重複する数字があれば、i-1のサブセットをすべて追加する以外に、nums[i]の前にk個の数字が同じであれば、ではi-1サブセットに前のk個の重複数を含む集合にnum[i]を加えてiのサブセットを加えることにしても,自分では解法が思いつかない.
参考:https://blog.csdn.net/feliciafay/article/details/18977055
遡及書きで重さを消すのは簡単ですが、重複数の中で最も多くの数字が含まれていることを考慮しなければならないのは最初だけなので、後のものは考慮する必要はありません.
コード:
タイトルの説明:
重複要素を含む可能性のある整数配列numsを指定し、その配列のすべての可能なサブセット(べき乗セット)を返します.
説明:解セットに重複するサブセットを含めることはできません.
例:
入力:[1,2,2]出力:[[2],[1],[1,2,2],[1,2],[1,2],[]
問題解決方案:
この問題は最初はどうやって自分と通れないのか分からなかったが、ダイナミックな計画で書かなければならなかった.ルールは、i-1のサブセットをすべて追加してから、i-1のサブセットを追加する各セットの後ろにnums[i]を追加することですが、ダイナミックプランニングが難しく、重複する数字があれば、i-1のサブセットをすべて追加する以外に、nums[i]の前にk個の数字が同じであれば、ではi-1サブセットに前のk個の重複数を含む集合にnum[i]を加えてiのサブセットを加えることにしても,自分では解法が思いつかない.
参考:https://blog.csdn.net/feliciafay/article/details/18977055
遡及書きで重さを消すのは簡単ですが、重複数の中で最も多くの数字が含まれていることを考慮しなければならないのは最初だけなので、後のものは考慮する必要はありません.
コード:
class Solution {
public:
vector> result;
vector> subsetsWithDup(vector& nums) {
sort(nums.begin(), nums.end());
vector temp;
result.push_back(temp);
getAns(0, nums, result, temp);
return result;
}
void getAns(int start, vector& nums, vector> &result, vector temp)
{
if(start == nums.size() - 1)
{
temp.push_back(nums[start]);
result.push_back(temp);
}
else
{
for(int i = start; i < nums.size(); i ++)
{
while(i != 0 && i != start && nums[i] == nums[i - 1])
{
i ++;
}
if(i == nums.size())
break;
temp.push_back(nums[i]);
result.push_back(temp);
getAns(i + 1, nums, result, temp);
temp.pop_back();
}
}
}
};