C++で増加部分列をすべて求めるアルゴリズム

問題の概要

整数型の配列が与えられたとき、その配列から作られるすべての異なる増加部分列を求めることを考えます。ただし、増加部分列の長さは2以上でなければなりません。例えば、配列が [4, 6, 7, 7] の場合、出力は次のようになります。

[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7, 7], [4, 7, 7]]

解法のアプローチ

この問題は、バックトラッキング（深さ優先探索）を用いて効率的に解くことができます。手順は以下の通りです。

• すべての結果を格納するための配列 res を定義します。
• solve というメソッドを作成します。このメソッドは、nums 配列、開始位置 start、一時的な配列 temp を引数として受け取ります。
• temp のサイズが 1 より大きい場合、temp を res に追加します。
• 同一階層での重複を防ぐための集合 visited（set）を作成します。
• i を start から nums のサイズまでループさせます。
  • x := nums[i] とします。
  • x がすでに visited に含まれている場合は、以降の処理をスキップします。
  • x を visited に追加します。
  • temp が空であるか、temp の末尾の要素が x 以下である場合は、以下を実行します。
    • x を temp に追加します。
    • solve(nums, i + 1, temp) を再帰的に呼び出します。
    • temp の末尾から 1 要素を削除します（バックトラック）。
• メイン関数から solve(nums, 0, temp) を呼び出します。
• res を返します。

重複回避のポイント

各再帰呼び出し（同じ階層）内で、一度選択した値と同じ値を選ばないようにすることで、重複する部分列の生成を防いでいます。この仕組みにより、入力配列に重複した値が含まれていても、結果として得られる部分列が重複することはありません。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > 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 start, vector <int> temp){
       if(temp.size() > 1){
          res.push_back(temp);
       }
       set <int> visited;
       for(int i = start; i < nums.size(); i++){
          int x = nums[i];
          if(visited.count(x))continue;
          visited.insert(x);
          if(temp.empty() || temp[temp.size() - 1] <= x){
             temp.push_back(x);
             solve(nums, i + 1, temp);
             temp.pop_back();
          }
       }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
       res.clear();
       vector <int> temp;
       solve(nums, 0, temp);
       return res;
    }
};
main(){
    vector<int> v = {5,6,7,8};
    Solution ob;
    print_vector(ob.findSubsequences(v));
}

入力

[5, 6, 7, 8]

出力

[[5, 6],[5, 6, 7],[5, 6, 7, 8],[5, 6, 8],[5, 7],[5, 7, 8],[5, 8],[6, 7],[6, 7, 8],[6, 8],[7, 8]]

まとめ

このように、バックトラッキングと set による重複チェックを組み合わせることで、与えられた配列から長さ 2 以上の増加部分列をすべて漏れなく、かつ重複なく列挙することができます。計算量は部分列の候補数に依存するため、入力サイズが大きくなると指数的に増加しますが、この手法はこの種の列挙問題に対する標準的なアプローチです。