LeetCode -- Permutations
题目描述：
Given a collection of 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], and [3,2,1].
就是对给定的数组生成全排列。
思路：
本题主要是Back tracking 的一个基本应用。
1.对于nums的每个元素nums[i] ，i∈[0,n) ：
2.拿掉nums[i]，对子数组n进行递归：
2.1当nums只有两个元素时，直接返回它们的排列，即{num[0],nums[1]}和{nums[1],nums[0]}
2.2得到递归后的子集subSet，遍历subSet，把拿掉的nums[i]放在子集的第一位
3.把nums[i]放回去
实现代码：
Given a collection of 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], and [3,2,1].
就是对给定的数组生成全排列。
思路：
本题主要是Back tracking 的一个基本应用。
1.对于nums的每个元素nums[i] ，i∈[0,n) ：
2.拿掉nums[i]，对子数组n进行递归：
2.1当nums只有两个元素时，直接返回它们的排列，即{num[0],nums[1]}和{nums[1],nums[0]}
2.2得到递归后的子集subSet，遍历subSet，把拿掉的nums[i]放在子集的第一位
3.把nums[i]放回去
实现代码：
public class Solution {
public IList<IList<int>> Permute(int[] nums) {
return Collect(nums.ToList());
}
private IList<IList<int>> Collect(IList<int> nums)
{
if(nums.Count <= 1){
return new List<IList<int>>(){new List<int>(nums)};
}
if(nums.Count == 2){
return new List<IList<int>>(){new List<int>(){nums[0],nums[1]},new List<int>(){nums[1],nums[0]}};
}
var newSet = new List<IList<int>>();
for(var i = 0;i < nums.Count; i++){
// take out nums[i] and put at last for each sub set
var x = nums[i];
nums.RemoveAt(i);
var subSet = Collect(nums);
for(var k = 0;k < subSet.Count; k++){
subSet[k].Add(x);
newSet.Add(subSet[k]);
}
nums.Insert(i, x);
}
return newSet;
}
}