LeetCode 46. Permutations

Leetcode : Permutations
Diffculty：Medium

给一个不重复的整数集合，要求返回这个集合的所有排列组合顺序。
例如：
Input:
[1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路：
其实就是我们中学时候学过的排列组合问题。
解法的主要思路是使用回溯法，可以看做是对一个树的遍历。
具体的话，有两种方式：BFS 和 DFS 也就是深度优先和广度优先的遍历方式。

BFS：
这个思路最简单。就是每次只拿一个数，然后把这个数插入到已有数列的所有可能位置上，得到一组新数列。以此类推，一直到把最后一个插入完成得到的那组数列就是结果。
由此可知，我们最后结果个数是 (num.length-1)的阶乘个
比如现在有[1,2,3]。
1）们先拿1，放进去。得到的结果就是[[1]]。
2）到第二层，我们拿2。那么把2,放到[1]的可能位置，也就是一前一后。那么把2全部放进去以后，我们得到新数列[[1,2],[2,1]]
3）到第三层，拿到3，还按上面思路。3可以插入到，前中后三个位置，又有两个数组。那么就得到了六个结果。也就是上面例子的那样。

下面上代码：

// leetcode 执行结果 3ms - beats 82.59%
public static List<List<Integer>> permute_BFS(int[] nums){
        List<List<Integer>> tmpList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        tmpList.add(list);
        List<List<Integer>> result = new ArrayList<>();
        backtrack_BFS(result, tmpList, nums, 1);
        return result;
    }

private static void backtrack_BFS(List<List<Integer>> result, List<List<Integer>> list, int[] nums, int index){
        if(index == nums.length){
            result.addAll(list);  // 如果index到底了，则把结果加到result里返回
            return;
        }else{
            List<List<Integer>> tmpList = new ArrayList<>(list.size() * (index+1));
            int tmpNum = nums[index];
            for(List<Integer> subList : list){
                for(int i=0; i<=subList.size(); i++){
                    List<Integer> innerList = new LinkedList<>(subList);
                    innerList.add(i,tmpNum);
                    tmpList.add(innerList);
                }
            }
            //  每往下一层 index+1
            backtrack_BFS(result, tmpList, nums, index+1);
        }
    }

DFS：
这个思路是深度优先遍历。
利用递归一层一层往里走，并且往tmpList里加元素，直到tmpList的长度 == nums.length 说明已经找到了一种可能的组合。此时加到result里。并且return到上一层。
推测由于在往里添加元素时，每次都需要判断子集合里是否已存在。所以这里会有一些耗时。时间没有BFS短。

下面上代码：

// leetcode 执行结果 4ms - beats 47.75%
public static List<List<Integer>> permute_DFS(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack_DFS(result, new LinkedList<>(), nums);
        return result;
    }

private static void backtrack_DFS(List<List<Integer>> list, List<Integer> tmpList, int[] nums){
        if(tmpList.size() == nums.length){
            // 已找到一种组合结果，加都result里，返回上一层
            list.add(new ArrayList<>(tmpList));
            return;
        }else{
            for(int i=0; i<nums.length; i++){
                if(tmpList.contains(nums[i])){  // 这里拖慢了时间
                    continue;
                }
                tmpList.add(nums[i]);
                backtrack_DFS(list, tmpList, nums);

    // 这里很重要
    // 因为该元素之前固定排列的所有结果都已经找到了。所以要移除，方便下一层找下一种组合结果。
                tmpList.remove(tmpList.size() - 1); 
            }
        }
    }

最后编辑于：2018.11.14 15:05:29