LeetCode-77.グループ（関連話題：遡及アルゴリズム）

二つの整数nとkを指定して、可能なk個の数の組み合わせを1...nに返します。
例:

  : n = 4, k = 2
  :
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

問題の筋道：深さ優先＋遡及アルゴリズム
javaコード:

class Solution {
    public List> combine(int n, int k) {
        List> res = new LinkedList<>();
        boolean[] f = new boolean[n];
        List tmp = new ArrayList<>(k);

        dfs(k, 0, n, f, tmp, res);

        return res;
    }
    private void dfs(int left, int s, int n, boolean[] f, List tmp, List> res) {
        if(0 == left) {
            res.add(tmp);
            return;
        }

        for(int i = s; i < n; i++) {
            if(f[i])
                continue;

            f[i] = true;
            List t = new ArrayList<>(tmp);
            t.add(i+1);
            dfs(left-1, i+1, n, f, t, res);

            f[i] = false;
        }
    }
}

注：Listはポインタ伝達であるため、深さ検索のたびに、格納結果サブセットのlist（tmp）をコピーする必要があるが、このような効率は低く、上記コードの実行時間は150+msである。
上記のコードを最適化して、深さ検索するたびに、結果のサブセットのlist（すなわちtmp）をcopyではなく、tmpがある結果のサブセットであると判断した場合、copyのtmpを結果セットに保存します。コードは以下の通りです。

class Solution {
    public List> combine(int n, int k) {
        List> res = new LinkedList<>();
        boolean[] f = new boolean[n];
        List tmp = new ArrayList<>(k);

        dfs(k, 0, n, f, tmp, res);

        return res;
    }
    private void dfs(int left, int s, int n, boolean[] f, List tmp, List> res) {
        if(0 == left) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        for(int i = s; i < n; i++) {
            if(f[i])
                continue;

            f[i] = true;
            tmp.add(i+1);
            dfs(left-1, i+1, n, f, tmp, res);

            f[i] = false;
            tmp.remove(tmp.size()-1);
        }
    }
}

運行時間は25 msぐらいです。