leetCode：Subsets

leetCodeの「Subsets」を解いてみた。
https://leetcode.com/problems/subsets/

この問題は、引数で与えられたintの配列について、全ての部分集合を返すというもの。
再帰を使って書くと簡単そうに思えたので、再帰を使って書いてみた。numsを前から辿りながら、index番目を選択する場合としない場合とに分けて処理している。

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        helper(ans, cur, nums, 0);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> cur, int[] nums, int index) {
        // 終了条件
        if (index == nums.length) {
            ans.add(cur);
            return;
        }

        // index番目の要素を選択しない場合
        helper(ans, cur, nums, index + 1);

        // index番目の要素を選択する場合
        List<Integer> copied = new ArrayList<>(cur);
        copied.add(nums[index]);
        helper(ans, copied, nums, index + 1);
    }

helper()の中でListを複製しているのは、引数の cur をいじってしまうと、他の再帰での探索に影響が出るため。(うまく説明できないが、自分の中のイメージはこんな感じ・・)

結果は以下となった。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Subsets.
Memory Usage: 39 MB, less than 5.74% of Java online submissions for Subsets.

速度は十分であるが、消費メモリが多いようだ。。やっぱり、原因は helper() の中でリストを複製しているところかな・・。ここは後で別の方法を考えたいと思う。

2020/07/11 追記
以下のような書き方もできる。速度や消費メモリ量は、上記のコードと大して変わらないが、こちらの方が一般的な書き方かもしれない。

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        helper(ans, cur, nums, 0);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> cur, int[] nums, int index) {
        // 終了条件
        if (index == nums.length) {
            // cur は使い回すので、複製してから ans に格納。
            ans.add(new ArrayList<>(cur));
            return;
        }

        // index 番目の要素を選択しない場合
        helper(ans, cur, nums, index + 1);

        // index 番目の要素を選択する場合
        cur.add(nums[index]);
        helper(ans, cur, nums, index + 1);
        cur.remove(cur.size() - 1); // バックトラッキング
    }