Solving the LeetCode "Permutations II" Problem in Go

Difficulty: Medium | Tags: Array, Backtracking, Sorting

Introduction

The "Permutations II" problem requires generating all unique permutations of an array that may contain duplicate elements. Unlike the standard permutations problem, handling duplicates efficiently is crucial to avoid redundant results.

Problem Analysis

Given an array of integers with possible duplicates, the task is to return all unique permutations. For example, for the input [1,1,2], the output should include [1,1,2], [1,2,1], and [2,1,1], but no duplicates of these permutations.

Solution Approach

To solve this problem, we use a backtracking approach combined with sorting to skip duplicate elements. The steps are as follows:

1. Sort the input array to group duplicates together.
2. Use a backtracking function to generate permutations while skipping duplicates.
3. Track used elements to avoid reusing the same element in the same permutation.

Go Implementation

package main
import (
"fmt"
"sort"
)
func permuteUnique(nums []int) [][]int {
    var result [][]int
    sort.Ints(nums)
    backtrack(&result, nums, []int{}, make([]bool, len(nums)))
    return result
}
func backtrack(result *[][]int, nums, current []int, used []bool) {
    if len(current) == len(nums) {
        temp := make([]int, len(current))
        copy(temp, current)
        *result = append(*result, temp)
        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
        current = append(current, nums[i])
        backtrack(result, nums, current, used)
        used[i] = false
        current = current[:len(current)-1]
    }
}
func main() {
    fmt.Println(permuteUnique([]int{1, 1, 2}))
    fmt.Println(permuteUnique([]int{1, 2, 3}))
}

Complexity Analysis

Time Complexity: O(N * N!), where N is the number of elements in the input array. The sorting step takes O(N log N), but the dominant factor is the backtracking step, which generates N! permutations.

Space Complexity: O(N), due to the recursion stack and the auxiliary array used to track visited elements.

Testing and Examples

Test cases include:

• Input: [1,1,2] → Output: [[1,1,2], [1,2,1], [2,1,1]]
• Input: [1,2,3] → Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
• Edge Case: [1] → Output: [[1]]

Best Practices and Tips

Key takeaways:

• Always sort the input array to handle duplicates efficiently.
• Use a boolean array to track used elements and avoid reusing them in the same permutation.
• Skip duplicates by checking if the current element is the same as the previous and the previous is unused.