46. Permutations #
题目 #
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
题目大意 #
给定一个没有重复数字的序列，返回其所有可能的全排列。
解题思路 #
- 求出一个数组的排列组合中的所有排列，用 DFS 深搜即可。
代码 #
package leetcode
func permute(nums []int) [][]int {
if len(nums) == 0 {
return [][]int{}
}
used, p, res := make([]bool, len(nums)), []int{}, [][]int{}
generatePermutation(nums, 0, p, &res, &used)
return res
}
func generatePermutation(nums []int, index int, p []int, res *[][]int, used *[]bool) {
if index == len(nums) {
temp := make([]int, len(p))
copy(temp, p)
*res = append(*res, temp)
return
}
for i := 0; i < len(nums); i++ {
if !(*used)[i] {
(*used)[i] = true
p = append(p, nums[i])
generatePermutation(nums, index+1, p, res, used)
p = p[:len(p)-1]
(*used)[i] = false
}
}
return
}