【leetcode】全排列

【leetcode】全排列

题目：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路：

利用回溯法，注意当递归到底，往res中新增元素时，注意需要new一个ArrayList，因为递归过程中传递的list由于回溯过程中变量的手动回溯过程，其指向的值是一直在变化的。我们需要记录的是递归到底时list中存放的是什么值。

时间复杂度: O(n !)级别的，其中n为nums数组的长度，

空间复杂度: O(n)级别的。

java代码：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        permute(res, nums, new ArrayList<>());
        return res;
    }
 
    private <E> void permute(List<List<Integer>> res, int[] nums, ArrayList<Integer> list) {
        if (list.size() == nums.length) {
            //需要new一个ArrayList，因为递归过程中传递的list
            // 由于回溯过程中变量的手动回溯过程，其指向的值是一直在变化的
            res.add(new ArrayList<>(list));
            return;
        }
 
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
 
            list.add(nums[i]);
            permute(res, nums, list);
            list.remove(list.size() - 1);
        }
    }
}