算法每日一练 (11)
💢欢迎来到张胤尘的技术站
💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥
文章目录
- 算法每日一练 (11)
- 全排列
- 题目描述
- 解题思路
- 解题代码
- `c/c++`
- `golang`
- `lua`
官方站点: 力扣 Leetcode
算法每日一练 (11)
全排列
题目地址:全排列
题目描述
给定一个不含重复数字的数组 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
中的所有整数 互不相同
解题思路
- 整体解题流程采用回溯的思路。
- 首先递归终止条件,如果当前状态已经满足了子集的条件,则返回到上一层。在本题中,递归终止条件就是当前索引到达了数组末尾,则无需向下继续递归。
- 紧接着就是在递归的过程中,枚举所有可能的选择,并针对每种情况都进行处理。
- 从当前索引开始,尝试交换每个位置的元素,然后递归的调用
backtrack
方法处理每一种情况。 - 紧接着回溯是关键步骤,在每次递归返回后,需要撤销当前的选择,恢复到上一步的状态,以便尝试其他可能性。
- 最后当所有的排列全部列举完毕后,返回
result
结果集即可。
解题代码
c/c++
#include <vector>
class Solution
{
public:
std::vector<std::vector<int>> permute(std::vector<int> &nums)
{
std::vector<std::vector<int>> result;
std::vector<int> current = nums;
backtrack(result, current, 0);
return result;
}
private:
void backtrack(std::vector<std::vector<int>> &result, std::vector<int> ¤t, int start)
{
if (start == current.size())
{
result.push_back(current);
return;
}
for (int i = start; i < current.size(); ++i)
{
std::swap(current[start], current[i]);
backtrack(result, current, start + 1);
std::swap(current[start], current[i]);
}
}
};
golang
func permute(nums []int) [][]int {
result := [][]int{}
backtrack(&result, &nums, 0)
return result
}
func backtrack(result *[][]int, current *[]int, start int) {
sz := len(*current)
if start == sz {
perm := make([]int, sz)
copy(perm, *current)
*result = append(*result, perm)
return
}
for i := start; i < sz; i++ {
(*current)[i], (*current)[start] = (*current)[start], (*current)[i]
backtrack(result, current, start+1)
(*current)[i], (*current)[start] = (*current)[start], (*current)[i]
}
return
}
lua
local function copyTable(t)
local copy = {}
for i = 1, #t do
copy[i] = t[i]
end
return copy
end
local function backtrack(result, current, start)
local sz = #current
if sz == start then
table.insert(result, copyTable(current))
return
end
for i = start, sz do
current[i], current[start] = current[start], current[i]
backtrack(result, current, start + 1)
current[i], current[start] = current[start], current[i]
end
end
local function permute(nums)
local result = {}
backtrack(result, nums, 1)
return result
end
🌺🌺🌺撒花!
如果本文对你有帮助,就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容,请随时向我提问。