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:
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:
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:
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
}
