Leetcode - Permutations && Permutations-ii
violet
posted @ Mar 18, 2020 04:43:15 AM
in 胡扯
with tags
Algorithm Golang backtracking Permutations
, 267 阅读
https://leetcode.com/problems/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] ]
https://leetcode.com/problems/permutations-ii/
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
func permute(nums []int) [][]int {
result := [][]int{}
backtrack(nums, &result, &[]int{})
return result
}
func backtrack(nums []int, result *[][]int, tmp *[]int) {
if len(*tmp) == len(nums) {
list := make([]int, len(*tmp))
copy(list, *tmp)
*result = append(*result, list)
return
}
for i := 0; i < len(nums); i++ {
if contains(*tmp, nums[i]) {
continue
}
*tmp = append(*tmp, nums[i])
backtrack(nums, result, tmp)
*tmp = (*tmp)[:len(*tmp)-1]
}
}
func contains(nums []int, num int) bool {
for _, n := range nums {
if n == num {
return true
}
}
return false
}
func permuteUnique(nums []int) [][]int {
result := [][]int{}
sort.Ints(nums)
used := make([]bool, len(nums))
backtrack(nums, &result, &[]int{}, &used)
return result
}
func backtrack(nums []int, result *[][]int, tmp *[]int, used *[]bool) {
if len(*tmp) == len(nums) {
list := make([]int, len(nums))
copy(list, *tmp)
*result = append(*result, list)
return
}
for i := 0; i < len(nums); i++ {
if (*used)[i] || (i > 0 && nums[i] == nums[i-1] && !(*used)[i-1]) {
continue
}
(*used)[i] = true
*tmp = append(*tmp, nums[i])
backtrack(nums, result, tmp, used)
(*used)[i] = false
*tmp = (*tmp)[:len(*tmp)-1]
}
}
Jul 19, 2021 11:18:15 AM
It has always been my belief that good writing like this takes research and talent. It’s very apparent you have done your homework. Great job!
Sep 02, 2022 02:40:25 PM
HP Board Model Paper 2023 Class 1 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. HPBOSE Question Paper Class 1 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.