LeetCode 2020-11-12: Permutations II

LeetCode daily challenge の問題 Permutations II (medium) の挑戦メモです。

問題の概要

• 与えられた数値の配列 (数値の重複が存在しうる) を並び替えて得られるすべての順列を列挙する

考え方

• これは値の重複がなければ簡単にとけるけど、重複があるのでちょっと面倒ですね…
  • それぞれの数値の個数をカウントし、それを補助情報として利用するのがよさそう
  • 基本的には再帰処理で「数値を一つ選ぶ」という操作をさせよう
    • ただし複数個存在する数値の場合は、「一つ選んだ数値を一個、二個、三個… と選べるだけ選ぶ」という操作にすればいいかな？
  • また再帰処理において、一つ (コールスタック的に) 前の再帰呼び出しで利用した数値は連続して利用しないように制約を設けておこう
    • これで同じ順列が列挙されてしまうのを防げるはず
• 実装して submit → 1 回 wrong answer → accept
  • Runtime 1ms で Your runtime beats 99.00 % of java submissions.
  • あと 1ms 削りたかったが、ちょっとの試行錯誤では無理だった 😿

コード

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] counts = new int[21];
        for (int i = 0; i < nums.length; i++) {
            counts[nums[i] + 10]++;
        }

        List<List<Integer>> result = new ArrayList<>();
        listPermutationRecursive(counts, nums.length, -1, new ArrayList<>(), result);

        return result;
    }

    void listPermutationRecursive(int[] counts, int len, int lastNum, List<Integer> work, List<List<Integer>> result) {
        if (work.size() == len) {
            result.add(new ArrayList<>(work));
            return;
        }

        for (int i = 0; i < counts.length; i++) {
            if (i != lastNum && counts[i] > 0) {
                int count = counts[i];
                for (int j = 1; j <= count; j++) {
                    counts[i]--;
                    work.add(i - 10);
                    listPermutationRecursive(counts, len, i, work, result);
                }

                for (int j = 0; j < count; j++) {
                    work.remove(work.size() - 1);
                }
                counts[i] = count;
            }
        }
    }
}