【算法刷题 | 回溯思想 07】4.18（全排列、全排列 ||）-11.全排列

11.1题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

• 示例一：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

• 示例二：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

11.2解法：回溯

11.2.1回溯思路

（1）函数返回值以及参数

private void backing(int[] nums)

（2）函数返回值

if(paths.size()==nums.length){
	res.add(new ArrayList(paths));
    return;
}

（3）遍历过程

for(int i=0;i<nums.length;i++){
	if(isUsed[i]==true)	{
        //该元素已经用过了
        continue;
    }
    isUsed[i]==true;
    paths.add(nums[i);
    backing(nums);
                   
    //回溯
    isUsed[i]=false;
    paths.remove(paths.size()-1);
}

11.2.2代码实现

	List<List<Integer>> res=new ArrayList<>();
    List<Integer> paths=new ArrayList<>();
    boolean[] isUsed;

    public List<List<Integer>> permute(int[] nums) {
        isUsed=new boolean[nums.length];
        Arrays.fill(isUsed,false);
        backing(nums);
        return res;
    }

    private void backing(int[] nums){
        if(paths.size()==nums.length){
        	res.add(new ArrayList(paths));
            return;
        }
        for(int i=0;i<nums.length;i++){
	        if(isUsed[i]==true)	{
                //该元素已经用过了
                continue;
            }
            isUsed[i]=true;
            paths.add(nums[i]);
            backing(nums);

            //回溯
            isUsed[i]=false;
            paths.remove(paths.size()-1);
        }
    }