[LeetCode] 46. Permutations

轉自LeetCode

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

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

<Solution>

這題是要求所有的可能排列

最間單的做法，就是用 c++ 自帶的 next_permutation

但要注意的是，next_permutation 是用 lexicographically 來做排列

也就是說，如果 input 是 [3,2,1]，那麼 next_permutation 是不會再做任何排列了

因為這在字典順序來說，[3,2,1] 是這三個數的排列組合中最大的一個

而題目是要求所有的排列組合，所以使用前要先 sort

因為 increasing order 在字典順序來說，是最小的

這樣去排列的時候，才會得到所有的排列組合

code 如下

那如果不要用 next_permutation 這個函式，要自己寫的話

就使用 DFS 的觀念，每一次遞迴就 swap 兩個數，去求所有的組合

code 如下
c++

kotlin