47. 全排列 II == 剑指 Offer 38. 字符串的排列

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1： 我面过：shopee考过
输入：nums = [1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]

  1. func permuteUnique(nums []int) (ans [][]int) {
  2.     sort.Ints(nums)
  3.     n := len(nums)
  4.     perm := []int{}
  5.     vis := make([]bool, n)
  6.     var backtrack func(int)
  7.     backtrack = func(idx int) {
  8.         if idx == n {
  9.             ans = append(ans, append([]int(nil), perm...))
  10.             return
  11.         }
  12.         for i, v := range nums {
  13.             if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
  14.                 continue
  15.             }
  16.             perm = append(perm, v)
  17.             vis[i] = true
  18.             backtrack(idx + 1)
  19.             vis[i] = false
  20.             perm = perm[:len(perm)-1]
  21.         }
  22.     }
  23.     backtrack(0)
  24.     return
  25. }

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”

//回溯，事件O(N!N),空间On
func permutation(s string) (ans []string) {
    t := []byte(s)
    sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
    n := len(t)

    perm := make([]byte, 0, n)
    vis := make([]bool, n)
    var backtrack func(int)

    backtrack = func(i int) {
        if i == n {
            ans = append(ans, string(perm))
            return
        }

        for j, b := range vis {
            if b || j > 0 && !vis[j-1] && t[j-1] == t[j] {
                continue
            }
            vis[j] = true

            perm = append(perm, t[j])
            backtrack(i + 1)
            perm = perm[:len(perm)-1]
            vis[j] = false
        }
    }
    backtrack(0)
    return
}

image.png