15. 全排列
    給定一個數(shù)字列表，返回其所有可能的排列。

樣例
給出一個列表[1,2,3]，其全排列為：

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
這里我想到了兩種寫法: 1:笛卡爾積后去重,2:嵌套循環(huán),忽略上層循環(huán)使用過的數(shù)

1:笛卡爾積后去重

 public static void main(String[] args) {
       //demo(1);
     
        ArrayList<Integer> source = new ArrayList<>();
        source.add(3);
        source.add(2);
        source.add(1);
        Collections.sort(source);
        sortDemo(source, 1, new ArrayList<>(),new ArrayList<>());
       
    }

 public static void sortDemo(List<Integer> nums, int index, List<Integer> i,List<List<Integer>> result) {
        
        for (int num : nums) {
            if (!i.contains(num)) {
                if (index == nums.size()) {
                    ArrayList<Integer> arrayList = new ArrayList<>(i);
                    arrayList.add(num);
                    result.add(arrayList);
                    System.out.println(arrayList);

                } else {
                    //注意!!! index + 1  不等于 index ++
//注意index ++,不等于index +1;  index +1 等價于 a = index +1;所以index+1 實際是一個臨時變量
                    ArrayList<Integer> temp = new ArrayList<>(i);
                    temp.add(num);
                    SortDemo(nums, index + 1, temp,result);
                }
            }
        }
        //System.out.println(result.size());
    }

2:嵌套循環(huán),忽略上層循環(huán)使用過的數(shù)

public static void main(String[] args) {
        List<List<Integer>> result = new ArrayList<>();

        dfs(new int[]{1,2,3},new boolean[3],new ArrayList<>(),result);
        result.forEach(c -> System.out.println(c));
    }

    private static void dfs(int[] nums,
                     boolean[] visited,
                     List<Integer> permutation,
                     List<List<Integer>> results) {
        if (nums.length == permutation.size()) {
            results.add(new ArrayList<Integer>(permutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }

            permutation.add(nums[i]);
            visited[i] = true;
            dfs(nums, visited, permutation, results);
            visited[i] = false;
            permutation.remove(permutation.size() - 1);
        }
    }