描述

給出一組數(shù)字，返回該組數(shù)字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以數(shù)字在數(shù)組中的位置靠前為優(yōu)先級(jí)，按字典序排列輸出。）

數(shù)據(jù)范圍：數(shù)字個(gè)數(shù)?0<n≤6

要求：空間復(fù)雜度?O(n!)，時(shí)間復(fù)雜度?O(n!）

示例1

輸入：

[1,2,3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

輸入：

[1]

返回值：

[[1]]

思路分析：

經(jīng)典的回溯算法問題——全排列（Permutations）

• permute?方法：這是類的公共方法，接收一個(gè)整數(shù)數(shù)組?num?作為輸入，并返回一個(gè)?ArrayList<ArrayList<Integer>>?類型的列表，其中每個(gè)內(nèi)部列表代表?num?數(shù)組的一個(gè)排列。

  • 初始化一個(gè)?ArrayList<ArrayList<Integer>>?類型的?result?列表，用于存儲(chǔ)所有排列。
  • 初始化一個(gè)?LinkedList<Integer>?類型的?list，用于在回溯過(guò)程中構(gòu)建當(dāng)前的排列。
  • 調(diào)用?backTrack?方法開始回溯過(guò)程。

• backTrack?方法：這是一個(gè)私有方法，用于遞歸地生成所有排列。它接收三個(gè)參數(shù)：

  • num：原始整數(shù)數(shù)組。

  • list：當(dāng)前正在構(gòu)建的排列（以鏈表形式）。

  • result：用于存儲(chǔ)所有排列的列表。

  • 遞歸終止條件：如果?list?的大小等于?num?的長(zhǎng)度，說(shuō)明已經(jīng)構(gòu)建了一個(gè)完整的排列，此時(shí)將這個(gè)排列（通過(guò)?new ArrayList<Integer>(list)?轉(zhuǎn)換為不可變列表）添加到?result?中，并返回。

  • 遞歸過(guò)程：遍歷?num?數(shù)組中的每個(gè)元素，如果當(dāng)前元素已經(jīng)存在于?list?中，則跳過(guò)該元素（避免重復(fù)排列）。否則，將該元素添加到?list?中，并遞歸調(diào)用?backTrack?方法繼續(xù)構(gòu)建下一個(gè)元素。遞歸返回后，需要撤銷上一步的選擇（即移除?list?中最后添加的元素），以便嘗試其他可能的排列。

代碼：

import java.util.*;public class Solution {public ArrayList<ArrayList<Integer>> permute(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<>();LinkedList<Integer> list = new LinkedList<>();backTrack(num, list, result);return result;}private void backTrack(int[] num, LinkedList<Integer> list,ArrayList<ArrayList<Integer>> result) {if (list.size() == num.length) {result.add(new ArrayList<Integer>(list));return;}for (int i = 0; i < num.length; i++) {if (list.contains(num[i])) {continue;}list.add(num[i]);backTrack(num, list, result);list.removeLast();}}
}