leetcode46. 全排列

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/permutations

題目描述

給定一個不含重復數(shù)字的數(shù)組 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 中的所有整數(shù) 互不相同

解題思路

排列問題本身就是讓你窮舉元素的位置
以[1,2,3]為例;

就是窮舉每個元素可以出現(xiàn)在任何位置,
我們用回溯算法的框架去做這道題:

首先看下回溯算法的框架::
result = []
void process(選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷選擇

回到本題中.我們要做的選擇,就是讓每個位置上的元素可以出現(xiàn)在任何位置上.
對回溯框架稍加改造,就可以做出這道題了.

代碼演示

class Solution {
	//記錄答案
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        process(nums,0);
        return ans;
    }
	/**
	* 回溯算法
	* index 數(shù)組下標.遞歸到的位置
	*/
    public void process(int[]nums,int index){
    //base case 
        if(index == nums.length){
            ans.add(toList(nums)); 
            return ;   
        }
        //可以進行的選擇
        for(int i= index;i < nums.length;i++){
        	//全排列是對元素出現(xiàn)位置的窮舉,因此我們把他交換到別的位置上,繼續(xù)進行遞歸,
        	//來讓他去出現(xiàn)在不同的位置上
        	//這一步就是做選擇,
            swap(nums,i,index);
            process(nums,index + 1);
            //撤銷選擇
            swap(nums,i,index);
        }
    }
	/**
	* 交換
	*/
    public void swap(int[]nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
	/**
	* 數(shù)組轉(zhuǎn)換成 List
	*/
    public List<Integer> toList(int[]nums){
        List<Integer> ans = new ArrayList<>();
        for(int a : nums){
            ans.add(a);
        }
        return ans;
    }
}

回溯算法專題

leetcode78 子集

leetcode77. 組合

leetcode40. 組合總和 II

leetcode90. 子集 II

leetcode216. 組合總和 III

leetcode39. 組合總和文章來源地址http://www.zghlxwxcb.cn/news/detail-500277.html

到了這里，關于leetcode46. 全排列(回溯算法-java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！