leetcode 46 全排列

leetcode 46 原題鏈接-- 全排列

題目描述：
給定一個(gè)不含重復(fù)數(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ù) 互不相同

回溯算法 也就是遞歸。

遞歸是解決這一類問題的通用解法。全排列。全部組合。
實(shí)際上就是一個(gè)決策樹的遍歷過程，站在回溯樹的一個(gè)節(jié)點(diǎn)上，你只需要思考 3 個(gè)問題：
1、路徑：也就是已經(jīng)做出的選擇。
2、選擇列表：也就是你當(dāng)前可以做的選擇。
3、結(jié)束條件：也就是到達(dá)決策樹底層，無法再做選擇的條件。

結(jié)構(gòu)：

result = []
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return

for 選擇 in 選擇列表:
    做選擇
    backtrack(路徑, 選擇列表)
    撤銷選擇

代碼演示

 /**
     * 主方法調(diào)用
     * @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){
        //結(jié)束條件，到數(shù)組最后面，已經(jīng)沒有數(shù)字可以選擇了，所以加入答案。
        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;
    }

    /**
     * 數(shù)組轉(zhuǎn)成集合，構(gòu)造返回體
     * @param nums
     * @return
     */
    public static List<Integer> toList(int[]nums){
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : nums){
            list.add(i);
        }
        return list;
    }

遞歸–打印一個(gè)字符串的全部排列(java)

遞歸–字符串的全部子序列和不重復(fù)的子序列（java）文章來源地址http://www.zghlxwxcb.cn/news/detail-474431.html

到了這里，關(guān)于leetcode--回溯算法.全排列(java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！