LeetCode 解答 #47. Permutations II プログラミング練習

問題：

難易度:　medium
入力:　 int型Array
目的: 入力されたArrayの数字の可能なすべての組み合わせを求めよ
出力:　int型のリストのリスト

前回の#46問目と殆ど同じ問題です。
どちらも可能な組み合わせをすべて探す問題です。
違いは今回の問題の入力が重複ありだと言う点です。
本質的な部分は違いないのでやはり全体探索が必要な問題となります。

注意すべき事:　

• 入力に重複数字が存在する

• 重複した答えが内容に気を付ける

以下回答です。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(nums, res, list, visited);
        return res;
    }
    
    public void backtracking(int[] nums, List<List<Integer>> res, List<Integer> list, boolean[] visited) {
        if (list.size() == nums.length) {
            res.add(new ArrayList(list));
            return;
        }
        for (int i=0; i<nums.length; i++) {
            if(i != 0 && nums[i] == nums[i-1] && visited[i-1]) continue;
            if (!visited[i]) {
                visited[i] = true;
                list.add(nums[i]);
                backtracking(nums, res, list, visited);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }
}

重複あり問題なので処理をする前にソートをすると重複数字が隣になるので処理しやすくなります。
Bfsで全体探索し、Listに追加していく。
visitedのArrayを追加し、この数字はすでに探索済みかどうかを記録する。
graphサーチにすることで重複をなくす。
Listの長さが入力Arrayと同じ長さの場合resに追加。
すべてのノードを探索終えれば終了。

今日は以上。
よいプログラミング生活を！