leetcode--回溯算法.全排列(java)-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode--回溯算法.全排列(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

leetcode 46 全排列

leetcode 46 原题链接-- 全排列

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

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

示例2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例3：
输入：nums = [1]
输出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

回溯算法也就是递归。

递归是解决这一类问题的通用解法。全排列。全部组合。
实际上就是一个决策树的遍历过程，站在回溯树的一个节点上，你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

结构：

result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

代码演示

 /**
     * 主方法调用
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>() ;
        process(nums,0,ans);
        return ans;
    }

    /**
     * 递归
     * @param nums
     * @param index
     * @param ans
     */
    public static void process(int[]nums,int index,List<List<Integer>> ans){
        //结束条件，到数组最后面，已经没有数字可以选择了，所以加入答案。
        if(index == nums.length){
            ans.add(toList(nums));
        }else{
            for (int i = index;i < nums.length;i++){
                //交换做出选择
                swap(nums,i,index);
                process(nums,index+1,ans);
                //撤销选择
                swap(nums,i,index);
            }
        }

    }

    /**
     * 全排列就是要交换所有的顺序去排列
     * @param nums
     * @param i
     * @param j
     */
    public static void swap(int[]nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 数组转成集合，构造返回体
     * @param nums
     * @return
     */
    public static List<Integer> toList(int[]nums){
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : nums){
            list.add(i);
        }
        return list;
    }