46. 全排列

Contents

1. 1. 题目
2. 2. 解题思路
   1. 2.1. 思路1
   2. 2.2. 思路2

题目

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

回溯思维，深度遍历+剪枝
一度是原来数组的长度
返回条件是到达数组的长度
一度是存储的数字，
剪枝是判断在原来的空间里

解题思路

思路1

思路1，看参考答案
先遍历first，first依次与其他位进行交换，然后遍历数组下一位，first+1，直到结束
执行用时 :7 ms, 在所有 Java 提交中击败了19.51%的用户 内存消耗 :39 MB, 在所有 Java 提交中击败了50.24%的用户

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        int first = 0;
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for(int num : nums){
            list.add(num);
        }      
        backtrace(n,first,list,result);
        return result;
    }
    public void backtrace(int n,int first,List<Integer> list , List<List<Integer>> result){
        if(first == n){
            result.add(new ArrayList<>(list));
        }
        for(int i = first ; i< n ; i++){
            Collections.swap(list,first,i);
            backtrace(n,first+1,list,result);
            Collections.swap(list,first,i);
        } 
    }
}

思路2

思路就是回溯，传入要遍历的数组
执行用时 :4 ms, 在所有 Java 提交中击败了64.83%的用户 内存消耗 :38.6 MB, 在所有 Java 提交中击败了62.61%的用户

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list =new ArrayList<>();
        List<Integer> input = new ArrayList<Integer>();
        for (int i : nums)
        {
            input.add(i);
        }
        backtrack(input,list,nums.length);
        return result;
    }
    public void backtrack(List<Integer> input,List<Integer> list,int length){
        if(list.size() == length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0 ; i< input.size() ; i++){
            Integer one = input.get(i);
            list.add(one);
            List<Integer> newList = new ArrayList(input);
            newList.remove(i);
            backtrack(newList,list,length);
            list.remove(list.size()-1);
        }
    }
}