AlgoPressAppearance
0046-全排列
https://leetcode.cn/problems/permutations
给定一个不含重复数字的数组 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 中的所有整数 互不相同
基本思路
回溯法
result = []
backtrack(paths, index)
if( 满足退出条件 )
//add to result
return
for item in 选择列表
if( isValid())
// add to path 做选择
backtrack(paths, index+1)
// remove from path 撤销选择
参考代码
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
//回溯法
List<int> curList = new List<int>();
private void AddToResult(List<int> list){
List<int> myList = new List<int>();
for(int i = 0; i<list.Count; i++){
myList.Add(list[i]);
}
result.Add(myList);
}
private void backtrack(int[] nums,int index){
//退出条件
if(index >= nums.Length){
AddToResult(curList);
return;
}
for(int i=0; i<nums.Length; i++){
if(!curList.Contains(nums[i])){
curList.Add(nums[i]);
backtrack(nums,index+1);
curList.Remove(nums[i]);
}
}
}
public IList<IList<int>> Permute(int[] nums) {
backtrack(nums,0);
return result;
}
}
参考代码2： 简化拷贝数组逻辑
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int[] nums, List<int> list){
if(list.Count == nums.Length){
//输出结果
result.Add(new List<int>(list.ToArray()));
return;
}
for(int i=0; i<nums.Length; i++){
if(!list.Contains(nums[i])){
list.Add(nums[i]);
dfs(nums,list);
list.RemoveAt(list.Count-1);
}
}
}
public IList<IList<int>> Permute(int[] nums) {
List<int> list = new List<int>();
dfs(nums,list);
return result;
}
}