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

問題：

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

入力Arrayのすべての可能な組み合わせを求める問題です。
すべての組み合わせを求めるのでどの道全体探索しなければなりません。
典型的なBacktracking, bfsの問題です。
重複な探索をしないように注意しましょう。

注意すべき事:　

• 入力に重複した数字はない

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

以下回答です。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(nums, list, res);
        return res;
    }
    
    public void dfs(int[] nums, List<Integer> list, List<List<Integer>> res) {
        if (list.size() == nums.length){
            res.add(new ArrayList(list));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if (!list.contains(nums[i])) {
                list.add(nums[i]);
                dfs(nums, list, res);
                if (list.size() > 0) list.remove(list.size() - 1);
       　 }
　　}
    }
}

Bfsで全体探索し、Listに追加していく。
既に追加している数字は飛び越し。
Listの長さが入力Arrayと同じ長さの場合resに追加。
すべてのノードを探索終えれば終了。

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