Wonderland
  • README.md
  • Notebook
    • Crypto
      • Solana
        • Troubleshooting
          • BPF SDK path does not exist
    • Language
      • Rust
        • Reference
          • Capturing the Environment with Closures
          • Understanding &mut &mut Reference
      • C++
        • Reference
          • Code for MS rand() and srand() in VC++ 6.0
  • Textbook
    • Serials
      • A Real-Time Cryptocurrency Ticker Dashboard
        • 0 - Some Preparation
    • Frontend
      • A Simple Progress Bar
      • A React Ribbon Component
      • An Easy to Use React DnD Sortable Component
      • Sticky Header, Sticky Footer and Fluid Content
      • How To Set Same Height As Width In CSS
  • dictionary
    • Alphabet
      • MySQL
      • FFmpeg
    • Algorithm
      • Diary
        • 2022
          • 07
            • 2022-07-02
            • 2022-07-01
          • 06
            • 2022-06-30
            • 2022-06-29
            • 2022-06-28
            • 2022-06-27
            • 2022-06-26
            • 2022-06-25
            • 2022-06-24
            • 2022-06-23
            • 2022-06-22
            • 2022-06-21
            • 2022-06-20
            • 2022-06-19
            • 2022-06-18
            • 2022-06-17
            • 2022-06-16
            • 2022-06-15
            • 2022-06-14
            • 2022-06-13
            • 2022-06-12
            • 2022-06-11
            • 2022-06-10
            • 2022-06-09
            • 2022-06-08
            • 2022-06-07
            • 2022-06-06
            • 2022-06-05
            • 2022-06-04
            • 2022-06-03
            • 2022-06-02
            • 2022-06-01
          • 05
            • 2022-05-31
            • 2022-05-30
            • 2022-05-29
            • 2022-05-28
            • 2022-05-27
            • 2022-05-26
            • 2022-05-25
            • 2022-05-24
            • 2022-05-23
            • 2022-05-22
            • 2022-05-21
            • 2022-05-20
            • 2022-05-19
            • 2022-05-18
            • 2022-05-17
            • 2022-05-16
            • 2022-05-15
    • Troubleshooting
      • A Weird Python Command Not Found Problem
Powered by GitBook
On this page
  • 77. Combinations
  • Description
  • Solution
  • 46. Permutations
  • Description
  • Solution
  • 784. Letter Case Permutation
  • Description
  • Solution
  1. dictionary
  2. Algorithm
  3. Diary
  4. 2022
  5. 05

2022-05-25

Last updated 2 years ago

Description

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

  • 1 <= n <= 20

  • 1 <= k <= n

Solution

Approach #0: DFS

func combine(n int, k int) [][]int {
    res := [][]int{}
    item := []int{}
    var dfs func(int)
    dfs = func(start int) {
        if len(item) == k {
            a := make([]int, k)
            copy(a, item)
            res = append(res, a)
            return
        }
        for i := start; i <= n; i++ {
            item = append(item, i)
            dfs(i + 1)
            item = item[:len(item)-1]
        }
    }
    dfs(1)
    return res
}

Approach #1: Alphabetical Order

func combine(n int, k int) [][]int {
    var temp []int
    for i := 1; i <= k; i++ {
        temp = append(temp, i)
    }
    temp = append(temp, n+1)

    var res [][]int
    for j := 0; j < k; {
        item := make([]int, k)
        copy(item, temp[:k])
        res = append(res, item)

        for j = 0; j < k && temp[j]+1 == temp[j+1]; j++ {
            temp[j] = j + 1
        }
        temp[j]++
    }
    return res
}

Description

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6

  • -10 <= nums[i] <= 10

  • All the integers of nums are unique.

Solution

Approach #0

func permute(nums []int) [][]int {
    var res [][]int
    var item []int
    m := make(map[int]struct{})

    n := len(nums)
    var dfs func([]int, map[int]struct{})
    dfs = func(item []int, m map[int]struct{}) {
        if len(item) == n {
            a := make([]int, n)
            copy(a, item)
            res = append(res, a)
            return
        }
        for i := 0; i < n; i++ {
            if _, ok := m[nums[i]]; ok {
                continue
            }
            item = append(item, nums[i])
            m[nums[i]] = struct{}{}
            dfs(item, m)
            delete(m, nums[i])
            item = item[:len(item)-1]
        }
    }
    dfs(item, m)
    return res
}

Approach #1

func permute(nums []int) [][]int {
    var res [][]int

    n := len(nums)
    var backtrack func(int)
    backtrack = func(first int) {
        if first == n {
            a := make([]int, n)
            copy(a, nums)
            res = append(res, a)
            return
        }
        for i := first; i < n; i++ {
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]
        }
    }
    backtrack(0)
    return res
}

Description

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

Constraints:

  • 1 <= s.length <= 12

  • s consists of lowercase English letters, uppercase English letters, and digits.

Solution

Approach #0: Too Slow

func letterCasePermutation(s string) []string {
    sList := []rune(s)
    n := len(s)

    var res []string
    var backtrace func(int)
    backtrace = func(start int) {
        if start == n {
            res = append(res, string(sList))
            return
        }
        for i := start; i < len(sList); i++ {
            backtrace(i + 1)
            if !unicode.IsLetter(sList[i]) {
                continue
            }
            if unicode.IsLower(sList[i]) {
                sList[i] = unicode.ToUpper(sList[i])
                backtrace(i + 1)
                sList[i] = unicode.ToLower(sList[i])
            }
            if unicode.IsUpper(sList[i]) {
                sList[i] = unicode.ToLower(sList[i])
                backtrace(i + 1)
                sList[i] = unicode.ToUpper(sList[i])
            }
        }
    }
    backtrace(0)

    m := make(map[string]struct{})
    var a []string
    for _, ss := range res {
        if _, ok := m[ss]; ok {
            continue
        }
        a = append(a, ss)
        m[ss] = struct{}{}
    }
    return a
}

Approach #1: Much Better

func letterCasePermutation(s string) []string {
    res := []string{""}
    for _, ch := range s {
        n := len(res)
        if unicode.IsLetter(rune(ch)) {
            for i := 0; i < n; i++ {
                res = append(res, res[i]+string(unicode.ToLower(rune(ch))))
                res[i] = res[i] + string(unicode.ToUpper(rune(ch)))
            }
        } else {
            for i := 0; i < n; i++ {
                res[i] = res[i] + string(ch)
            }
        }
    }
    return res
}

77. Combinations
46. Permutations
784. Letter Case Permutation