【C++】重複する要素を含む配列の順列をすべて求める方法（Permutations II）

問題の概要

整数のコレクションが与えられたとき、そのすべての順列（並べ替えのパターン）を求めることを考えます。ただし、配列に重複した要素が含まれている場合は、見た目が同じ順列は結果から除外する必要があります。

例えば、配列が [1, 1, 3] の場合、期待される出力は次のようになります。

[[1,1,3], [1,3,1], [3,1,1]]

解法のアプローチ：バックトラッキング（再帰）

この問題は、再帰的なバックトラッキングを使うことで効率的に解くことができます。基本的な手順は以下の通りです。

1. リストとインデックス idx を引数に取る再帰関数を用意します。最初は idx = 0 から開始します。
2. idx がリストのサイズと等しくなったら、その時点のリストを結果配列 res に追加して処理を終了します。
3. i を idx からリストの末尾までループさせます。
   • nums[i] == nums[idx] かつ i != idx の場合は、同じ順列が生成されるため、その要素はスキップします。
   • nums[i] と nums[idx] を入れ替えます。
   • solve(nums, idx + 1) を呼び出して再帰的に処理を続けます。
4. 事前に配列をソートしておくことで、重複チェックを正しく機能させます。最後に res を返します。

C++での実装例

以下に実際の実装コードを示します。

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}

class Solution {
public:
    vector < vector <int> > res;
    void solve(vector <int> nums, int idx = 0){
        if(idx == nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i = idx; i <nums.size(); i++){
            if(nums[i] == nums[idx] && i != idx)continue;
            swap(nums[i], nums[idx]);
            solve(nums, idx + 1);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res.clear();
        sort(nums.begin(), nums.end());
        solve(nums);
        return res;
    }
};

main(){
    Solution ob;
    vector<int> v = {1,1,3};
    print_vector(ob.permuteUnique(v));
}

実行結果

入力

[1,1,3]

出力

[[1,1,3],[1,3,1],[3,1,1]]

ポイントの解説

• ソートの重要性： permuteUnique() 内で sort() を呼び出しているのは、同じ値の要素を隣接させるためです。これにより、重複チェックの条件 nums[i] == nums[idx] が正しく機能します。
• 重複のスキップ： 同じ位置に同じ値が来るパターンは既に探索済みのため、continue でスキップすることで無駄な計算を省き、重複した順列が結果に含まれるのを防いでいます。
• 計算量： 要素数を n とすると、最悪の場合の時間計算量は O(n × n!) となります。重複が多い配列では、スキップによって実際の探索数は大幅に削減されます。