天天看點

【LeetCode】 46. 全排列 回溯 JAVA

題目

題目傳送門:傳送門(點選此處)

【LeetCode】 46. 全排列 回溯 JAVA
題解

思路

思考這道題目,很容易想到回溯,了解很容易,如下圖

【LeetCode】 46. 全排列 回溯 JAVA

是以代碼寫起來,也相對的簡單,不過話又說回來,這道題其實不難,還是要多刷一刷題,找到更加合适的解決方案,這個方案依舊不是最優解

代碼

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);
        }
    }

}