給定一個不含重復數字的陣列 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]]
存放于陣列A的n個元素，生成其排列：
- 第一個元素不動，生成后面n-1個元素的排列；
- 第一、第二個元素互換，生成后面n-1個元素的排列；
- 最后，第一個、第n個元素互換，生成后面n-1個元素的排列
為生成后面n-1個元素的排列，繼續采取下面的步驟：
- 第二個元素不動，生成后面n-2個元素的排列；
- 第二、第三個元素互換，生成后面n-2個元素的排列；
- 最后，第二個、第n個元素互換，生成后面n-2個元素的排列；
當排列的前n-2個元素已確定后，為生成后面2個元素的排列，可以：
-
第n-1個元素不動，生成后面1個元素的排列，此時，n個元素已構成排列；
-
第n-1、第n個元素互換，生成后面1個元素的排列，此時，n個元素已構成排列；
Java代碼
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
int n = nums.length;
backtrack(n, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// 所有數都填完了
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// 動態維護陣列
Collections.swap(output, first, i);
// 繼續遞回填下一個數
backtrack(n, output, res, first + 1);
// 撤銷操作
Collections.swap(output, first, i);
}
}
}
注:
(1)以下是java.util.Collections.swap()方法的宣告，
public static void swap(List<?> list,int i,int j)
引數
- ? list-- 在該串列中的調劑元素，
- ? i-- 要交換的一個元素的索引，
- ? j-- 要交換的其它元素的索引，
(2)
軟體維護主要是指根據需求變化或硬體環境的變化對應用程式進行部分或全部的修改
C++代碼
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有數都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 動態維護陣列
swap(output[i], output[first]);
// 繼續遞回填下一個數
backtrack(res, output, first + 1, len);
// 撤銷操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
以上代碼轉自力扣題解，筆者自己畫圖總結出來的決議，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/510844.html
標籤：Java
上一篇：自定義映射resultMap