LeetCode: Permutations II

// https://code.dennyzhang.com/permutations-ii
// Basic Ideas: backtracking
//
// Complexity: Time O(n!), Space O(1)
import "sort"

func dfs(combination []int, visited []bool, nums []int, res *[][]int) {
    if len(combination) == len(nums) {
        combination2 := make([]int, len(combination))
        copy(combination2, combination)
        *res = append(*res, combination2)
        return
    }

    for i, b := range visited {
        if b { 
            continue
        }
        // avoid duplicated caculation
        if i>0 && nums[i-1] == nums[i] && ! visited[i-1] {
            continue
        }
        combination = append(combination, nums[i])
        visited[i] = true
        dfs(combination, visited, nums, res)
        visited[i] = false
        combination = combination[0:len(combination)-1]
    }
}

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)        
    res := [][]int{}
    visited := make([]bool, len(nums))
    dfs([]int{}, visited, nums, &res)
    return res
}