46. 全排列

給定一個不含重復數(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ù)?互不相同

解題思路：

遞歸回溯（Recursion、Backtrack）

class Solution {public List<List<Integer>> permute(int[] nums) {// 遞歸回溯// Time: O(n x n!)// Space: O(n)List<List<Integer>> res = new ArrayList<>();backtrack(nums, 0, res);return res;}private void backtrack(int[] nums, int start, List<List<Integer>> res) {// 如果當前位置已經(jīng)是數(shù)組的末尾，說明已經(jīng)生成了一個排列，將其加入結(jié)果列表if (start == nums.length) {List<Integer> permutation = new ArrayList<>();for (int num : nums) {permutation.add(num);}res.add(permutation);return;}// 將當前位置的數(shù)字與后面的數(shù)字交換，并遞歸生成下一個位置的排列for (int i = start; i < nums.length; i++) {// 交換當前位置的數(shù)字與后面的數(shù)字swap(nums, start, i);// 遞歸生成下一個位置的排列backtrack(nums, start + 1, res);// 恢復原始狀態(tài)，以便進行下一次交換swap(nums, start, i);}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}