【LeetCode】 46. 全排列回溯 JAVA

心已赠人 2021-06-10 20:38 494阅读 0赞

题目

题目传送门：传送门（点击此处）
在这里插入图片描述

题解

思路

思考这道题目，很容易想到回溯，理解很容易，如下图
在这里插入图片描述
所以代码写起来，也相对的简单，不过话又说回来，这道题其实不难，还是要多刷一刷题，找到更加合适的解决方案，这个方案依旧不是最优解

代码

class Solution { 
    List<List<Integer>> res;
    int[] nums;
    public List<List<Integer>> permute(int[] nums) { 
        this.res = new ArrayList<>();
        this.nums = nums;
        // Arrays.sort(nums); // not necessary
        backtrack(new ArrayList<>());
        return res;
    }
    private void backtrack(List<Integer> tempList) { 
        if (tempList.size() == nums.length) { 
            res.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) { 
            if (tempList.contains(nums[i])) continue;
            tempList.add(nums[i]);
            backtrack(tempList);
            tempList.remove(tempList.size() - 1);
        }
    }
}