https://leetcode.com/problems/permutations/submissions/1009963724/
46. Permutations
給你一個陣列 nums，求出所有的排列。
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
思路：
1.昨天是組合今天是排列，dfs 所有可能的結果，如果這個元素前面已經排列過就
跳過（用一個 Set 紀錄）。
2..如果目前隊列的大小等於 nums 長度就把結果加入到結果集。
Java Code：
---------------------------------------
class Solution {
private List<List<Integer>> res;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<>();
dfs(nums, new ArrayList<>(), new boolean[nums.length]);
return res;
}
private void dfs(int[] nums, List<Integer> curr, boolean[] visited) {
int n = nums.length;
if (curr.size() == n) {
res.add(new ArrayList<>(curr));
return;
}
for (int i = 0; i < n; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
curr.add(nums[i]);
dfs(nums, curr, visited);
curr.remove(curr.size() - 1);
visited[i] = false;
}
}
}
---------------------------------------
--
https://i.imgur.com/DANRJFR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690953032.A.363.html
※ 編輯: Rushia (122.100.75.86 臺灣), 08/02/2023 13:10:41