重複を除外したサブセットの生成法

重複を除外したサブセットの生成法

テーブル：

1. イントロダクション
2. 問題の説明
3. ブルートフォースソリューション
4. 再帰の最適化
5. PseudocodeとJavaコード
6. C++コード

イントロダクション

こんにちはみなさん、チャンネルに戻ってきてくれてありがとう。皆さんがとてもうまくやっていることを願っています。今日はSDシートの問題、サブセットサム2の解決策を提案します。しかし、問題に進む前に、チャンネルに初めていらっしゃる方は、チャンネル登録をぜひぜひ考えてください。問題は次のように述べられています。与えられた配列numsは、重複する要素を含む可能性があります。あなたのタスクは、すべてのサブセットを返すことですが、解決策のセットには重複するサブセットが含まれてはいけません。解答は任意の順序で返すことができます。例えば、配列「one, two, two」を見ると、8つのサブセットが得られます。この問題は以前のビデオで既に解決済みでしたが、そのときはすべてのサブセットを印刷する必要がありました。そして、nが3の場合、2のn乗のサブセットが常に存在することを確認しました。しかし、ここでは重複するサブセットを無視しなければなりません。したがって、これらが与えられた配列のサブセットになります。もし、この問題が面接で出たら、インタビューアに最初に提案する解決策は、ピックとノンピックの技術を使用して2のn乗の全てのサブセットを生成することです。ピックとノンピックの技術を知らない場合は、以前のビデオを見てください。それによって、これらのサブセットを生成できます。2のn乗のサブセットを生成したら、それらをセットに入れることで重複を除去できます。セットに入れることで重複がなくなり、ユニークなサブセットだけが残ります。その後、このセットをリストのリストまたはベクトルのベクトルに変換し、それを返すことで答えになります。再帰の後で使用される追加の時間がかかりますが、追加の処理として、セットに追加してからそのリストをリストのリストに戻すために、追加の時間がかかります。このセットのサイズは2のn乗であるため、要素をセットに入れるためにmに対してmログmの時間がかかります。インタビュアは、セットに要素を追加する余分な手順に満足しないでしょう。そして、再帰自体を最適化するように求めるでしょう。

問題の説明

SDシートの問題「サブセットサム2」では、重複を除外したサブセットの解を求める必要があります。問題では、与えられた配列numsには重複が含まれる可能性があります。この配列から、重複のないサブセットを返す必要があります。また、サブセットの順序は任意です。例えば、配列[1, 2, 2]の場合、8つのサブセットが得られます。以前のビデオでサブセットの生成方法を確認しましたが、今回は重複するサブセットを無視する必要があります。

ブルートフォースソリューション

問題に対する最初の解決策は、ブルートフォースです。この解決策では、ピックとノンピックのテクニックを使用して2のn乗のすべてのサブセットを生成する方法をインタビュアに説明します。ピックとノンピックのテクニックについて詳しく知りたい場合は、前のビデオを見てください。このテクニックを使えば、すべてのサブセットを生成できます。ただし、生成されるサブセットには重複が含まれる可能性があります。したがって、生成されたすべてのサブセットをセットに入れることで、重複を除外します。最後に、このセットをリストのリストまたはベクトルのベクトルに変換して返します。再帰呼び出しの後に余分な時間がかかりますが、それはセットへの追加とリストへの戻しのためです。

再帰の最適化

再帰の最適化方法を考えましょう。ここでは、再帰呼び出しで重複するサブセットを避けることが目的です。最初のステップでは、空のデータ構造を持っています。これはサイズ0のリストです。次に、サイズ1のリストを生成するために、配列の要素を1つずつピックして再帰呼び出しを行います。この時点で、重複するサブセットを避けるロジックを挿入します。つまり、同じ要素を再びピックアップしないようにします。また、サイズ2のリスト、サイズ3のリストなど、すべてのサイズのサブセットを生成します。このロジックを次のレベルに拡張し、与えられた配列の要素をすべてピックアップして最終的な答えを作ります。この最適化により、重複するサブセットを生成せず、ユニークなサブセットのみを取得できます。

PseudocodeとJavaコード

以下が問題の解決のためのPseudocodeです。

function subsets(nums):
    sortedNums = sort(nums)
    answer = []

    function generateSubsets(index, dataStructure):
        answer.add(deepCopy(dataStructure))

        for i = index to len(sortedNums) - 1:
            if i != index and sortedNums[i] == sortedNums[i - 1]:
                continue

            dataStructure.add(sortedNums[i])
            generateSubsets(i + 1, dataStructure)
            dataStructure.removeLastElement()

    generateSubsets(0, emptyDataStructure)
    return answer

以下がPseudocodeを元にしたJavaコードです。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();

        generateSubsets(0, new ArrayList<>(), nums, answer);

        return answer;
    }

    private void generateSubsets(int index, List<Integer> dataStructure, int[] nums, List<List<Integer>> answer) {
        answer.add(new ArrayList<>(dataStructure));

        for (int i = index; i < nums.length; i++) {
            if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }

            dataStructure.add(nums[i]);
            generateSubsets(i + 1, dataStructure, nums, answer);
            dataStructure.remove(dataStructure.size() - 1);
        }
    }
}

C++コード

以下がC++コードです。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> answer;
        sort(nums.begin(), nums.end());

        generateSubsets(0, nums, answer, {});

        return answer;
    }

private:
    void generateSubsets(int index, vector<int>& nums, vector<vector<int>>& answer, vector<int> dataStructure) {
        answer.push_back(dataStructure);

        for (int i = index; i < nums.size(); i++) {
            if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }

            dataStructure.push_back(nums[i]);
            generateSubsets(i + 1, nums, answer, dataStructure);
            dataStructure.pop_back();
        }
    }
};

以上が、サブセットサム2の問題解決のための日本語の記事とコードです。このアルゴリズムを使用することで、重複しないユニークなサブセットを生成できます。この解決策は再帰を使用していますが、最適化されており、重複するサブセットを効率的に排除しています。