46. 全排列

一 题目：

二 思路：

• 涉及到一个位置数据放不放置会影响后续结果，我们都采用回溯的方法
• 每个位置放一个值，放完结束，已经放过的不能再放
  需要注意的一点是这里的cur我们不能用Set结构，不是因为res.add(new ArrayList<>(cur));的 接口限制cur不能传set，而是因为Set是无序的，尽管我们第二次迭代的时候先放了1，再放了0，但是我们res.add(new ArrayList<>(cur))这里set转list的时候因为无序性也会导致数据有问题。

三 代码：

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length<1){
            return res;
        }
        search(nums,new LinkedList<>());
        return res;
    }

    private void search(int[] nums, LinkedList<Integer> cur) {
        if (cur.size()==nums.length){
            res.add(new ArrayList<>(cur));
            return;
        }

        //curIndex位置设置值
        for (int i = 0; i <nums.length ; i++) {
            if (cur.contains(nums[i])){
                continue;
            }

            cur.add(nums[i]);
            search(nums,cur);
            cur.removeLast();
        }
    }
}