組合せを再帰で列挙してみた

# ある日、2個からn個までの組合せを列挙しなければならなくなりました。

例: {1, 2, 3, 4} -> {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}

forを重ねるだけではn重に対応できないので再帰で実装しました。

```java
import java.util.ArrayList;

public class Combination {
    // 全体集合
    private int[] a = {1, 2, 3, 4};
    // 添え字管理
    private ArrayList<Integer> idx = new ArrayList<>(); // 0:i, 1:j, 2:k, ...
    // 実行
    public Combination(){
        // combination(1, 1);
        combination(2, 2);
        combination(3, 3);
        combination(4, 4);
        // combination(5, 5);
    }

    public static void main(String[] args){
        new Combination();
    }

    // 2以上集合の大きさ以下の指定を想定する
    public void combination(int n, int size){
        if(n == 1){
            // 最も内側のループに相当
            // 添え字に従いa[]から組合せを出力
            for(int i=idx.get(size-n-1)+1;i<a.length;i++){
                for(int j=0;j<size-1;j++){
                    System.out.print(a[idx.get(j)]+",");   
                }
                System.out.println(a[i]);
            }
        }else if(n == size){
            // 最も外側のループに相当
            if(n <= 1 || a.length < n)System.exit(0);
            for(int i=0;i<a.length-(n-1);i++){
                // カウンタを更新                
                idx.add(size-n, i);
                combination(n-1, size);
            }
        }else{
            // 上二つの間に位置するループに相当
            for(int i=idx.get(size-n-1)+1;i<a.length-(n-1);i++){
                idx.add(size-n, i);
                combination(n-1, size);
            }
        }
    }
}
```

# わかりにくい点
再帰での実装のためカウンタを外部にListとして管理しています。0番目の要素が最も外側のループカウンタで、size-1番要素まで使用します。0番目から使いたかったので
```java
idx.add(size-n, i)
i=idx.get(size-n-1)+1
```
のようにsizeとの差をとっています。
```idx.get(size-n-1)```で一つ上のループカウンタにアクセスしています。

# 参考にした記事
https://qiita.com/5zm/items/949bf0721e8324f0ee35

カウンタの初期値や継続条件をどのように書くべきか悩んだときに参考になりました！:raised_hands:

## おわりに
もっと効率的な書き方があったら紹介してほしいです！
ありがとうございました！

### おまけ
出力例です。
<details><summary>すごく長い</summary><div>

```
1,2
1,3
1,4
2,3
2,4
3,4
1,2,3
1,2,4
1,3,4
2,3,4
1,2,3,4
```
```
1,2
1,3
1,4
1,5
1,6
1,7
1,8
2,3
2,4
2,5
2,6
2,7
2,8
3,4
3,5
3,6
3,7
3,8
4,5
4,6
4,7
4,8
5,6
5,7
5,8
6,7
6,8
7,8
1,2,3
1,2,4
1,2,5
1,2,6
1,2,7
1,2,8
1,3,4
1,3,5
1,3,6
1,3,7
1,3,8
1,4,5
1,4,6
1,4,7
1,4,8
1,5,6
1,5,7
1,5,8
1,6,7
1,6,8
1,7,8
2,3,4
2,3,5
2,3,6
2,3,7
2,3,8
2,4,5
2,4,6
2,4,7
2,4,8
2,5,6
2,5,7
2,5,8
2,6,7
2,6,8
2,7,8
3,4,5
3,4,6
3,4,7
3,4,8
3,5,6
3,5,7
3,5,8
3,6,7
3,6,8
3,7,8
4,5,6
4,5,7
4,5,8
4,6,7
4,6,8
4,7,8
5,6,7
5,6,8
5,7,8
6,7,8
1,2,3,4
1,2,3,5
1,2,3,6
1,2,3,7
1,2,3,8
1,2,4,5
1,2,4,6
1,2,4,7
1,2,4,8
1,2,5,6
1,2,5,7
1,2,5,8
1,2,6,7
1,2,6,8
1,2,7,8
1,3,4,5
1,3,4,6
1,3,4,7
1,3,4,8
1,3,5,6
1,3,5,7
1,3,5,8
1,3,6,7
1,3,6,8
1,3,7,8
1,4,5,6
1,4,5,7
1,4,5,8
1,4,6,7
1,4,6,8
1,4,7,8
1,5,6,7
1,5,6,8
1,5,7,8
1,6,7,8
2,3,4,5
2,3,4,6
2,3,4,7
2,3,4,8
2,3,5,6
2,3,5,7
2,3,5,8
2,3,6,7
2,3,6,8
2,3,7,8
2,4,5,6
2,4,5,7
2,4,5,8
2,4,6,7
2,4,6,8
2,4,7,8
2,5,6,7
2,5,6,8
2,5,7,8
2,6,7,8
3,4,5,6
3,4,5,7
3,4,5,8
3,4,6,7
3,4,6,8
3,4,7,8
3,5,6,7
3,5,6,8
3,5,7,8
3,6,7,8
4,5,6,7
4,5,6,8
4,5,7,8
4,6,7,8
5,6,7,8
1,2,3,4,5
1,2,3,4,6
1,2,3,4,7
1,2,3,4,8
1,2,3,5,6
1,2,3,5,7
1,2,3,5,8
1,2,3,6,7
1,2,3,6,8
1,2,3,7,8
1,2,4,5,6
1,2,4,5,7
1,2,4,5,8
1,2,4,6,7
1,2,4,6,8
1,2,4,7,8
1,2,5,6,7
1,2,5,6,8
1,2,5,7,8
1,2,6,7,8
1,3,4,5,6
1,3,4,5,7
1,3,4,5,8
1,3,4,6,7
1,3,4,6,8
1,3,4,7,8
1,3,5,6,7
1,3,5,6,8
1,3,5,7,8
1,3,6,7,8
1,4,5,6,7
1,4,5,6,8
1,4,5,7,8
1,4,6,7,8
1,5,6,7,8
2,3,4,5,6
2,3,4,5,7
2,3,4,5,8
2,3,4,6,7
2,3,4,6,8
2,3,4,7,8
2,3,5,6,7
2,3,5,6,8
2,3,5,7,8
2,3,6,7,8
2,4,5,6,7
2,4,5,6,8
2,4,5,7,8
2,4,6,7,8
2,5,6,7,8
3,4,5,6,7
3,4,5,6,8
3,4,5,7,8
3,4,6,7,8
3,5,6,7,8
4,5,6,7,8
1,2,3,4,5,6
1,2,3,4,5,7
1,2,3,4,5,8
1,2,3,4,6,7
1,2,3,4,6,8
1,2,3,4,7,8
1,2,3,5,6,7
1,2,3,5,6,8
1,2,3,5,7,8
1,2,3,6,7,8
1,2,4,5,6,7
1,2,4,5,6,8
1,2,4,5,7,8
1,2,4,6,7,8
1,2,5,6,7,8
1,3,4,5,6,7
1,3,4,5,6,8
1,3,4,5,7,8
1,3,4,6,7,8
1,3,5,6,7,8
1,4,5,6,7,8
2,3,4,5,6,7
2,3,4,5,6,8
2,3,4,5,7,8
2,3,4,6,7,8
2,3,5,6,7,8
2,4,5,6,7,8
3,4,5,6,7,8
1,2,3,4,5,6,7
1,2,3,4,5,6,8
1,2,3,4,5,7,8
1,2,3,4,6,7,8
1,2,3,5,6,7,8
1,2,4,5,6,7,8
1,3,4,5,6,7,8
2,3,4,5,6,7,8
1,2,3,4,5,6,7,8

```　
</div></details>