【回溯算法】【打卡第172道】:leetCode :46. 全排列

【回溯算法】【打卡第172道】:leetCode :46. 全排列 1、题目描述

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

2、算法分析

简单说下回溯算法。

回溯算法是基于递归算法的。树型结构很重要，大家一定要熟悉N叉树的递归思想。

N叉树的递归思想：当子树找不到的时候，子树会回溯到父节点继续找。这个思想在回溯算法总特别重要。

具体看图，子节点向父节点回溯，N叉树的递归思想。 

回溯思想：for循环是遍历的每一层的集合，纵向遍历的是树的深度递归。

回溯模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

本题思路：

①定义结果集List，和path，path是记录每一次的组合。

②创建boolean的used数组，因为是排列，所以used记录的是nums中的元素是否使用过

最最重要的是回溯函数：

①确定递归的终止条件当path.size() == nums.length的时候，也就从根结点到叶子结点找到这个排列的时候。将path添加到结果集中。

②遍历nums数组的时候，先判断当前元素是否使用过，若被使用过则继续下一个元素；若未被使用过则元素返回true；但是最后该元素的used[i] = false；因为下一个元素也要使用。

③注意：path.removeLast();是linkedList的一个方法，意思是删除并保留最后一个元素。

也就是回溯算法中比较重要的一步骤，子节点向父节点回溯。

removeLast：如下

public class Demo {
    public static void main(String[] args) {

        // create a linkedList
        linkedList list = new linkedList();

        // add some elements
        list.add("Hello");
        list.add(2);
        list.add("Chocolate");
        list.add("10");

        // print the list
        System.out.println("linkedList:" + list);

        // remove the last element
        System.out.println("Last element:" + list.removeLast());

        // print the list
        System.out.println("linkedList:" + list);
    }
}

// 结果为：
linkedList:[Hello, 2, Chocolate, 10]
Last element:10
linkedList:[Hello, 2, Chocolate]

3、代码实现

class Solution {
    List> result = new ArrayList<>();
    linkedList path = new linkedList<>();
    boolean[] used;
    public List> permute(int[] nums) {
        if(nums == null || nums.length == 0){
            return result;
        }
        // 记录nums中的元素是否使用过
        used = new boolean[nums.length];
        backTracking(nums);
        return result;
    }
    
    public void backTracking(int nums[]){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0;i < nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums);
            // 删除并保存最后一个元素，其实就是删除链表中的最后一个元素
            path.removeLast();
            // 因为是排序，后面的元素也需要用。
            used[i] = false;
        }
    }
}