全排列

题目

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

示例:

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

解题思路

此题可分为两个步骤来实现：

1. 先实现 1，2，3 三个数字的所有排列组合，用回溯的方式可以解决，代码也很好理解。

        for (int i = 0; i < nums.length; i++){
            tempArray.add(nums[i]);
            getSubList(resultArray,tempArray,nums);
            tempArray.remove(tempArray.size()-1);//回退一步继续执行
        }

结果为：[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]

2. 剪枝，因为初步得出的结果中出现了很多重复数字，比如[1,1,1],[2,2,2]等，而题目要求可不重复，那么就需要想办法去掉重复内容。

所以需要建立visited数组，用来标记同一个数组中某个数字是否使用过，如果使用过了就跳过执行。

        for (int i = 0; i < nums.length; i++){
            if (visited[i] == 1) continue;
            visited[i] = 1;
            tempArray.add(nums[i]);
            getSubList(resultArray,tempArray,nums);
            tempArray.remove(tempArray.size()-1);//回退一步继续执行
            visited[i] = 0;//回退访问记录，继续执行
        }

最终代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List list = new ArrayList();
        int[] visited = new int[nums.length];
        getSubList (list,new ArrayList(),visited,nums);
        return list;
    }

    public void getSubList (List res,List temp,int[] visited,int[] nums){
        if (temp.size() == nums.length){
            res.add(new ArrayList<>(temp));
            return ;
        }
        for (int i = 0; i < nums.length; i++){
            if (visited[i] == 1) continue; //代表某下标处对应的数字已经用过了，为了避免结果里出现重复数字，在此做剪枝操作。
            visited[i] = 1;
            temp.add(nums[i]);
            getSubList(res,temp,visited,nums);
            temp.remove(temp.size()-1);
            visited[i] = 0;
        }
    }
}