[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 如下

	class Solution {
	public:
	vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int>> ans;
	if(nums.empty()) {
	return ans;
	}
	//> sort first
	sort(nums.begin(), nums.end());
	do {
	ans.push_back(nums);
	} while(next_permutation(nums.begin(), nums.end()));
	return ans;
	}
	};

view raw allPermutation_1.cpp hosted with ❤ by GitHub

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

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

code 如下
c++

	class Solution {
	public:
	vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int>> ans;
	if(nums.empty()) {
	return ans;
	}
	permuteDFS(0, nums, ans);
	return ans;
	}
	void permuteDFS(const int &start, vector<int> &nums, vector<vector<int>> &ans) {
	if(start == nums.size()) {
	ans.push_back(nums);
	return;
	}
	for(int i = start; i < nums.size(); i++) {
	swap(nums[start], nums[i]);
	permuteDFS(start+1, nums, ans);
	swap(nums[start], nums[i]);
	}
	}
	};

view raw allPermutation_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun permute(nums: IntArray): List<List<Int>> {
	val ans = mutableListOf<List<Int>>()
	dfs(0, nums, emptyList(), ans)
	return ans
	}
	fun dfs(start: Int, nums: IntArray, cmb: List<Int>, ans: MutableList<List<Int>>) {
	if(cmb.size == nums.size) {
	ans.add(cmb)
	return
	}
	for(i in start until nums.size) {
	nums[start] = nums[i].also {nums[i] = nums[start]}
	dfs(start+1, nums, cmb+listOf(nums[start]), ans)
	nums[start] = nums[i].also {nums[i] = nums[start]}
	}
	}
	}

view raw permutations.kt hosted with ❤ by GitHub